one-indexed-vec 0.2.0

A one-based (1-indexed) wrapper around Vec<T>: element at position N is accessed via vec[N].
Documentation
//! Eigenvalue algorithms.

use crate::Vec1;
use crate::linear::matrix::Matrix;

impl Matrix<f64> {
    /// Power iteration to find the dominant eigenvalue and eigenvector.
    ///
    /// Returns `(eigenvalue, eigenvector)`.
    ///
    /// ```rust
    /// use one_indexed_vec::{vec1, linear::matrix::Matrix};
    ///
    /// // diag(3, 2): dominant eigenvalue is 3
    /// let a = Matrix::from_row_major(vec1![3.0, 0.0, 0.0, 2.0], 2, 2);
    /// let (lambda, _v) = a.power_iteration(1000, 1e-10);
    /// assert!((lambda - 3.0).abs() < 1e-6);
    /// ```
    pub fn power_iteration(&self, max_iter: usize, tol: f64) -> (f64, Vec1<f64>) {
        let n = self.rows();
        assert_eq!(n, self.cols(), "power_iteration: matrix must be square");

        let mut v = Vec1::with_capacity(n);
        for _ in 0..n {
            v.push(1.0 / libm::sqrt(n as f64));
        }

        let mut lambda = 0.0;
        for _ in 0..max_iter {
            // w = A · v
            let w = self.matvec(&v);

            // 归一化 w
            let mut norm = 0.0;
            for i in 1..=n {
                norm += w[i] * w[i];
            }
            norm = libm::sqrt(norm);
            let mut v_new = Vec1::with_capacity(n);
            for i in 1..=n {
                v_new.push(w[i] / norm);
            }

            // 瑞利商:λ = (A·v_new)·v_new
            let av = self.matvec(&v_new);
            let mut new_lambda = 0.0;
            for i in 1..=n {
                new_lambda += av[i] * v_new[i];
            }

            if (new_lambda - lambda).abs() < tol {
                return (new_lambda, v_new);
            }
            lambda = new_lambda;
            v = v_new;
        }
        (lambda, v)
    }

    /// Rayleigh quotient `vᵀ A v / vᵀ v` — a good estimate of an eigenvalue
    /// given an approximate eigenvector `v`.
    ///
    /// ```rust
    /// use one_indexed_vec::{vec1, linear::matrix::Matrix};
    ///
    /// let a = Matrix::from_row_major(vec1![3.0, 0.0, 0.0, 2.0], 2, 2);
    /// let v = vec1![1.0, 0.0];
    /// assert!((a.rayleigh_quotient(&v) - 3.0).abs() < 1e-10);
    /// ```
    pub fn rayleigh_quotient(&self, v: &Vec1<f64>) -> f64 {
        let av = self.matvec(v);
        let n = v.len();
        let mut num = 0.0;
        let mut den = 0.0;
        for i in 1..=n {
            num += v[i] * av[i];
            den += v[i] * v[i];
        }
        num / den
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::vec1;

    #[test]
    fn power_diagonal() {
        let a = Matrix::from_row_major(vec1![3.0, 0.0, 0.0, 2.0], 2, 2);
        let (lambda, _v) = a.power_iteration(1000, 1e-10);
        assert!((lambda - 3.0).abs() < 1e-6);
    }

    #[test]
    fn rayleigh_basic() {
        let a = Matrix::from_row_major(vec1![3.0, 0.0, 0.0, 2.0], 2, 2);
        let v = vec1![1.0, 0.0];
        assert!((a.rayleigh_quotient(&v) - 3.0).abs() < 1e-10);
    }
}