Answer to Question #257813 in Linear Algebra for kofi

Question

Consider the linear eigenproblem, 𝐴𝑥=𝜆𝑥, for the matrix

D=[1 1 2

2 1 1

1 1 3 ]

Solve for the largest eigenvalue by the direct method using the secant method. Let 𝜆^((0))=5 and 𝜆^((1))=4 Solve for the eigenvalues by the QR method

Answer 1

Part one

$D= \begin{pmatrix} 1&1 &2 \\ 2&1 & 1\\ 1&1&3 \end{pmatrix}$

Characteristic equation $det||D-\lambda\Iota||=0$

$Det \begin{pmatrix} 1-\lambda&1&2 \\ 2&1-\lambda&1\\ 1&1&3-\lambda \end{pmatrix}$

Characteristic polynomial is of the form;

$\lambda^3-A_1\lambda^2+A_2\lambda-A_3=0$

Where $A_1=$ sum of main diagonal element

$=1+1+3=5$

$A_2=$ sum of minors of the main diagonal element

$A_2= \begin{vmatrix} 1 & 1 \\ 1 & 3 \end{vmatrix}+\begin{vmatrix} 1 & 2 \\ 1 & 3 \end{vmatrix}+\begin{vmatrix} 1& 1 \\ 2 & 1 \end{vmatrix}=2+1-1=2$

$A_3= det(D)=\quad\quad\quad\quad1\begin{vmatrix} 1 & 1\\ 1 & 3 \end{vmatrix}-1\begin{vmatrix} 2& 1\\ 1 & 3 \end{vmatrix}+2\begin{vmatrix} 2& 1\\ 1& 1 \end{vmatrix}$

$=1(2)-1(5)+2(1)$

$=-1$

Characteristic polynomial is

$\lambda^3-5\lambda^2+2\lambda+1=0$

Let $\lambda^3-5\lambda^2+2\lambda+1=0$

$f(\lambda)=\lambda^3-5\lambda^2+2\lambda+1$

1st iteration

$\lambda_0=5$ and $\lambda_1=4$

$f(\lambda_0)=f(s)=11$

$f(\lambda_1)=f(4)=-7$

$\therefore\>\lambda_2=5-11$ $\frac{4-5}{-7-11}=4.3889$

$f(\lambda_2)=-1.9937$

2nd iteration

$\lambda_1=4$ and $\lambda_2=4.3889$

$f(\lambda_1)=f(4)=-7$

$f(\lambda_2)=f(4.3889)= -1.9937$

$\lambda_3=4-(-7)$ $\frac{4.3889-4}{-1.9937-(-7)}=4.5438$

3rd iteration

$\lambda_2=4.3889$ and $\lambda_3=4.5438$

$f(\lambda_2)=-1.9937$

$f(\lambda_3)=f(4.5438)=0.6688$

$\lambda_4=4.3889-(-1.9937)$

$\frac{4.5438-4.3889}{0.6688-\>-1.9937}$

$=4.5049$

$f(\lambda_4)=f(4.5049)=-0.0378$

4th iteration

$\lambda_3=4.5438$ and $\lambda_4=4.5049$

$f(\lambda_3)=0.6688$

$f(\lambda_4)=-0.0378$

$\lambda_5=4.5438-0.6688$

$\frac{4.5049-4.5438}{-0.0378-0.6688}$

$=4.5070$

$f(\lambda_5)=-0.0003$

Approximate root $=4.507$

Part two

$Q$ -$R$ method

Let $a_1= \begin{bmatrix} 1&2&1 \end{bmatrix}$ $a_2=\begin{bmatrix} 1&1& 1 \end{bmatrix}$

and

$a_3=\begin{bmatrix} 2&1 & 3 \end{bmatrix}$

Let orthogonal set $=\begin{pmatrix} b_1& b_2&b_3 \end{pmatrix}$

Let orthonormal set $=\begin{pmatrix} q_1&q_2& q_3 \end{pmatrix}$

Let $b_1= \begin{bmatrix} 1&2 & 1 \end{bmatrix},$

$||b_1||=\sqrt{1^2+2^2+1^2}=2.45$

$q_1=\frac{1}{2.45}\begin{bmatrix} 1&2 & 1 \end{bmatrix}=\begin{bmatrix} 0.41,&0.82,& 0.41 \end{bmatrix}$

$b_2=\begin{bmatrix} 1&1& 1 \end{bmatrix}-$

$<(1,1,1),(0.41,0.82,0.41)>(0.41,0.82,0.41)$

$=\begin{pmatrix} 0.33,&-0.33,&0.33 \end{pmatrix}$

$||b_2||= \sqrt{ 0.33^2+0.33^2+0.33^2}=$

$0.58$

$q_2= \frac{1}{0.58}\begin{bmatrix} 0.33,&-0.33& 0.33 \end{bmatrix}=$

$\begin{pmatrix} 0.58,&-0.58,&0.58 \end{pmatrix}$

$b_3=\begin{pmatrix} 2,&1,&3 \end{pmatrix}$ $-$

$-<(2,1,3),(0.41,0.82,0.41)>$

$(0.41,0.82,0.41)$

$- <(2,1,3),(0.58,-0.58,0.58)>$

$b_3=(-0.5,0,0.5)\quad ||b_3||=$

$\sqrt{0.5^2+0^2+0.5^2}=0.71$

$q_3=\frac{1}{0.71}(-0.5,0,0.5)=$

$(-0.71,0,0.71)$

$\therefore Q= \begin{bmatrix} q_1&q_2& q_3 \end{bmatrix}=$

$\begin{bmatrix} 0.41&0.58 & -0.71\\ 0.82&-0.58 & 0\\ 0.41&0.58&0.71 \end{bmatrix}$

$R=Q^TA=\begin{pmatrix} 0.41&0.82 & 0.41\\ 0.58&-0.58 & 0.58\\ -0.71&0&0.71 \end{pmatrix}\begin{pmatrix} 1&1 & 2\\ 2&1& 1\\ 1&1&3 \end{pmatrix}$

$=\begin{pmatrix} 2.45&1.63& 2.86\\ 0&0.58&2.31\\ 0&0&0.71 \end{pmatrix}$

Denoting the above $R$ as $R_0$ and the $Q$ as $Q_0$

Let $A_1=R_0Q_0$

Let $A_1=Q_1R_1$ be $QR$ factorization of $A_1$ and similarly create $A_2=R_1Q_1$

This process is continued until $A_m$ is created such that $A_m=Q_mR_m$ and $A_{m1}=R_mQ_m$ are equal.

At convergence, the diagonal entries below the main diagonal are sufficiently small.

The diagonal entries of $A_m$ will be eigenvalues of matrix $A$

The expected values will be approximate to $0.28514,0.77812 \>and \> 4 .50701$