Let
a
=
x
0
<
x
1
<
⋯
<
x
n
=
b
{\displaystyle a=x_{0}<x_{1}<\cdots <x_{n}=b\!\,}
[
a
,
b
]
{\displaystyle [a,b]\!\,}
q
(
x
)
{\displaystyle q(x)\!\,}
q
∈
C
1
[
a
,
b
]
{\displaystyle q\in C^{1}[a,b]\!\,}
[
x
i
,
x
i
+
1
]
{\displaystyle [x_{i},x_{i+1}]\!\,}
q
{\displaystyle q\!\,}
q
(
x
)
{\displaystyle q(x)\!\,}
(
x
0
,
y
0
)
,
(
x
1
,
y
1
)
,
…
,
(
x
n
,
y
n
)
{\displaystyle (x_{0},y_{0}),(x_{1},y_{1}),\ldots ,(x_{n},y_{n})\!\,}
Show that if we know
z
i
≡
q
′
(
x
i
)
,
i
=
0
,
…
,
n
{\displaystyle z_{i}\equiv q'(x_{i}),i=0,\ldots ,n\!\,}
q
{\displaystyle q\!\,}
Consider interval
[
x
i
,
x
i
+
1
]
{\displaystyle [x_{i},x_{i+1}]\!\,}
q
i
′
(
x
)
{\displaystyle q'_{i}(x)\!\,}
q
i
′
(
x
)
=
z
i
+
1
−
z
i
x
i
+
1
−
x
i
(
x
−
x
i
)
+
z
i
{\displaystyle q_{i}'(x)={\frac {z_{i+1}-z_{i}}{x_{i+1}-x_{i}}}(x-x_{i})+z_{i}\!\,}
q
i
(
x
)
=
z
i
x
+
z
i
+
1
−
z
i
x
i
+
1
−
x
i
(
x
−
x
i
)
2
2
+
K
i
{\displaystyle q_{i}(x)=z_{i}x+{\frac {z_{i+1}-z_{i}}{x_{i+1}-x_{i}}}{\frac {(x-x_{i})^{2}}{2}}+K_{i}\!\,}
q
i
(
x
)
=
z
i
(
x
−
x
i
)
+
z
i
+
1
−
z
i
x
i
+
1
−
x
i
(
x
−
x
i
)
2
2
+
y
i
{\displaystyle q_{i}(x)=z_{i}(x-x_{i})+{\frac {z_{i+1}-z_{i}}{x_{i+1}-x_{i}}}{\frac {(x-x_{i})^{2}}{2}}+y_{i}\!\,}
Since
q
{\displaystyle q\!\,}
[
a
,
b
]
{\displaystyle [a,b]\!\,}
q
i
−
1
(
x
i
)
=
q
i
(
x
i
)
=
y
i
{\displaystyle q_{i-1}(x_{i})=q_{i}(x_{i})=y_{i}\!\,}
z
i
−
1
(
x
i
−
x
i
−
1
)
+
z
i
−
z
i
−
1
x
i
−
x
i
−
1
(
x
i
−
x
i
−
1
)
2
2
+
y
i
−
1
=
y
i
{\displaystyle z_{i-1}(x_{i}-x_{i-1})+{\frac {z_{i}-z_{i-1}}{x_{i}-x_{i-1}}}{\frac {(x_{i}-x_{i-1})^{2}}{2}}+y_{i-1}=y_{i}\!\,}
z
i
=
−
z
i
−
1
+
2
(
y
i
−
y
i
−
1
)
x
i
−
x
i
−
1
i
=
1
,
…
n
{\displaystyle z_{i}=-z_{i-1}+{\frac {2(y_{i}-y_{i-1})}{x_{i}-x_{i-1}}}\quad i=1,\ldots n\!\,}
Q
k
R
k
=
A
k
{\displaystyle Q_{k}R_{k}=A_{k}\!\,}
A
k
+
1
=
R
k
Q
k
{\displaystyle A_{k+1}=R_{k}Q_{k}\!\,}
Q
k
R
k
=
A
k
−
χ
k
I
{\displaystyle Q_{k}R_{k}=A_{k}-\chi _{k}I\!\,}
A
k
+
1
=
R
k
Q
k
+
χ
k
I
{\displaystyle A_{k+1}=R_{k}Q_{k}+\chi _{k}I\!\,}
Suppose
A
m
=
U
T
A
U
{\displaystyle A_{m}=U^{T}AU}
U
{\displaystyle U}
R
m
=
Q
m
T
A
m
{\displaystyle R_{m}=Q_{m}^{T}A_{m}}
A
m
+
1
=
R
m
Q
m
=
Q
m
T
A
m
Q
m
=
Q
m
T
U
T
A
U
Q
m
{\displaystyle A_{m+1}=R_{m}Q_{m}=Q_{m}^{T}A_{m}Q_{m}=Q_{m}^{T}U^{T}AUQ_{m}}
which is as desired as
Q
m
U
{\displaystyle Q_{m}U}
For the shifted case, the same argument holds using the fact that
R
m
=
Q
m
T
(
A
m
−
χ
m
I
)
{\displaystyle R_{m}=Q_{m}^{T}(A_{m}-\chi _{m}I)}
Let
A
=
(
3
1
1
2
)
{\displaystyle A={\begin{pmatrix}3&1\\1&2\end{pmatrix}}\!\,}
Q
R
{\displaystyle QR\!\,}
A
{\displaystyle A\!\,}
χ
0
=
1
{\displaystyle \chi _{0}=1\!\,}
A
{\displaystyle A\!\,}
λ
1
=
1.382
,
λ
2
=
3.618
{\displaystyle \lambda _{1}=1.382,\lambda _{2}=3.618\!\,}
Q
=
(
c
−
s
s
c
)
{\displaystyle Q={\begin{pmatrix}c&-s\\s&c\end{pmatrix}}\!\,}
c
2
+
s
2
=
1
{\displaystyle c^{2}+s^{2}=1\!\,}
The shifted iteration appears to work better because its diagonal entries are closer to the actual eigenvalues than the diagonal entries of the unshifted iteration.
A
1
=
(
3.5
.5
.5
1.5
)
{\displaystyle A_{1}={\begin{pmatrix}3.5&.5\\.5&1.5\end{pmatrix}}\!\,}
A
1
=
(
3.6
.2
.2
1.4
)
{\displaystyle A_{1}={\begin{pmatrix}3.6&.2\\.2&1.4\end{pmatrix}}\!\,}
Let
A
{\displaystyle A\!\,}
N
×
N
{\displaystyle N\times N\!\,}
A
x
=
b
{\displaystyle Ax=b\!\,}
F
(
x
)
=
1
2
⟨
x
,
A
x
⟩
−
⟨
b
,
x
⟩
{\displaystyle F(x)={\frac {1}{2}}\langle x,Ax\rangle -\langle b,x\rangle \!\,}
⟨
⋅
,
⋅
⟩
{\displaystyle \langle \cdot ,\cdot \rangle \!\,}
R
N
{\displaystyle R^{N}\!\,}
F
{\displaystyle F\!\,}
x
v
+
1
=
x
v
+
α
v
d
v
{\displaystyle x_{v+1}=x_{v}+\alpha _{v}d_{v}\!\,}
When
x
v
{\displaystyle x_{v}\!\,}
d
v
{\displaystyle d_{v}\!\,}
α
v
{\displaystyle \alpha _{v}\!\,}
F
(
x
v
+
α
d
v
)
{\displaystyle F(x_{v}+\alpha d_{v})\!\,}
α
{\displaystyle \alpha \!\,}
r
v
{\displaystyle r_{v}\!\,}
α
v
=
⟨
r
v
,
d
v
⟩
⟨
d
v
,
A
d
v
⟩
,
r
v
=
b
−
A
x
v
{\displaystyle \alpha _{v}={\frac {\langle r_{v},d_{v}\rangle }{\langle d_{v},Ad_{v}\rangle }},\quad r_{v}=b-Ax_{v}\!\,}
Since
A
{\displaystyle A\!\,}
(
A
x
,
y
)
=
(
x
,
A
T
y
)
=
(
x
,
A
y
)
{\displaystyle (Ax,y)=(x,A^{T}y)=(x,Ay)\!\,}
Substitute into Functional
edit
F
(
x
v
+
α
d
v
)
=
1
2
⟨
x
v
+
α
d
v
,
A
x
v
+
α
A
d
v
⟩
−
⟨
b
,
x
v
+
α
d
v
⟩
=
⟨
d
v
,
A
d
v
⟩
2
α
2
+
α
⟨
d
v
,
A
x
v
⟩
−
α
⟨
b
,
d
v
⟩
+
1
2
⟨
x
v
,
A
x
v
⟩
−
⟨
b
,
x
v
⟩
{\displaystyle {\begin{aligned}F(x_{v}+\alpha d_{v})&={\frac {1}{2}}\langle x_{v}+\alpha d_{v},Ax_{v}+\alpha Ad_{v}\rangle -\langle b,x_{v}+\alpha d_{v}\rangle \\&={\frac {\langle d_{v},Ad_{v}\rangle }{2}}\alpha ^{2}+\alpha \langle d_{v},Ax_{v}\rangle -\alpha \langle b,d_{v}\rangle +{\frac {1}{2}}\langle x_{v},Ax_{v}\rangle -\langle b,x_{v}\rangle \end{aligned}}\!\,}
Take Derivative With Respect to Alpha
edit
F
′
(
x
v
+
α
d
v
)
=
⟨
d
v
,
A
d
v
⟩
α
+
⟨
d
v
,
A
x
v
⟩
−
⟨
b
,
d
v
⟩
{\displaystyle F'(x_{v}+\alpha d_{v})=\langle d_{v},Ad_{v}\rangle \alpha +\langle d_{v},Ax_{v}\rangle -\langle b,d_{v}\rangle \!\,}
Set Derivative Equal To Zero
edit
0
=
⟨
d
v
,
A
d
v
⟩
α
+
⟨
d
v
,
A
x
v
−
b
⟩
{\displaystyle 0=\langle d_{v},Ad_{v}\rangle \alpha +\langle d_{v},Ax_{v}-b\rangle \!\,}
α
=
⟨
d
v
,
r
v
⟩
⟨
d
v
,
A
d
v
⟩
{\displaystyle \alpha ={\frac {\langle d_{v},r_{v}\rangle }{\langle d_{v},Ad_{v}\rangle }}\!\,}
Let
{
d
j
}
j
=
1
N
{\displaystyle \{d_{j}\}_{j=1}^{N}\!\,}
A
{\displaystyle A\!\,}
R
N
{\displaystyle R^{N}\!\,}
⟨
d
j
,
A
d
k
⟩
=
0
,
j
≠
k
{\displaystyle \langle d_{j},Ad_{k}\rangle =0,j\neq k\!\,}
x
{\displaystyle x\!\,}
x
=
∑
j
=
1
N
x
j
^
d
j
{\displaystyle x=\sum _{j=1}^{N}{\hat {x_{j}}}d_{j}\!\,}
A
−
{\displaystyle A-\!\,}
d
j
{\displaystyle d_{j}\!\,}
x
^
j
{\displaystyle {\hat {x}}_{j}\!\,}
x
{\displaystyle x\!\,}
d
j
{\displaystyle d_{j}\!\,}
⟨
x
,
A
d
k
⟩
=
⟨
∑
j
=
1
n
x
^
j
d
j
,
A
d
k
⟩
=
∑
j
=
1
N
x
^
j
⟨
d
j
,
A
d
k
⟩
=
x
^
k
⟨
d
k
,
A
d
k
⟩
{\displaystyle {\begin{aligned}\langle x,Ad_{k}\rangle &=\langle \sum _{j=1}^{n}{\hat {x}}_{j}d_{j},Ad_{k}\rangle \\&=\sum _{j=1}^{N}{\hat {x}}_{j}\langle d_{j},Ad_{k}\rangle \\&={\hat {x}}_{k}\langle d_{k},Ad_{k}\rangle \end{aligned}}\!\,}
x
^
k
=
⟨
x
,
A
d
k
⟩
⟨
d
k
,
A
d
k
⟩
{\displaystyle {\hat {x}}_{k}={\frac {\langle x,Ad_{k}\rangle }{\langle d_{k},Ad_{k}\rangle }}\!\,}
Let
x
v
{\displaystyle x_{v}\!\,}
x
v
=
∑
j
=
1
v
−
1
x
^
j
d
j
,
v
=
2
,
3
,
…
{\displaystyle x_{v}=\sum _{j=1}^{v-1}{\hat {x}}_{j}d_{j},\quad v=2,3,\ldots \!\,}
x
v
+
1
=
x
v
+
x
^
v
d
v
{\displaystyle x_{v+1}=x_{v}+{\hat {x}}_{v}d_{v}\!\,}
x
^
v
{\displaystyle {\hat {x}}_{v}\!\,}
x
v
∈
span
{
d
1
,
d
2
,
…
,
d
v
−
1
}
{\displaystyle x_{v}\in {\mbox{span}}\{d_{1},d_{2},\ldots ,d_{v-1}\}\!\,}
A
{\displaystyle A\!\,}
d
j
{\displaystyle d_{j}\!\,}
x
^
v
{\displaystyle {\hat {x}}_{v}\!\,}
α
v
{\displaystyle \alpha _{v}\!\,}
x
^
v
=
⟨
r
v
,
d
v
⟩
⟨
d
v
,
A
d
v
⟩
=
α
v
{\displaystyle {\hat {x}}_{v}={\frac {\langle r_{v},d_{v}\rangle }{\langle d_{v},Ad_{v}\rangle }}=\alpha _{v}\!\,}
⟨
r
v
,
d
v
⟩
=
⟨
b
−
A
x
v
,
d
v
⟩
=
⟨
A
x
−
A
x
v
,
d
v
⟩
=
⟨
A
x
,
d
v
⟩
−
⟨
A
x
v
,
d
v
⟩
=
⟨
x
,
A
d
v
⟩
−
⟨
x
v
,
A
d
v
⟩
⏟
0
=
x
^
v
⟨
d
v
,
A
d
v
⟩
{\displaystyle {\begin{aligned}\langle r_{v},d_{v}\rangle &=\langle b-Ax_{v},d_{v}\rangle \\&=\langle Ax-Ax_{v},dv\rangle \\&=\langle Ax,d_{v}\rangle -\langle Ax_{v},d_{v}\rangle \\&=\langle x,Ad_{v}\rangle -\underbrace {\langle x_{v},Ad_{v}\rangle } _{0}\\&={\hat {x}}_{v}\langle d_{v},Ad_{v}\rangle \end{aligned}}\!\,}
x
^
v
=
⟨
r
v
,
d
v
⟩
⟨
d
v
,
A
d
v
⟩
{\displaystyle {\hat {x}}_{v}={\frac {\langle r_{v},d_{v}\rangle }{\langle d_{v},Ad_{v}\rangle }}\!\,}
![{\displaystyle [a,b]\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1ef1354dbfeea71ab05cf297ffc40786b7813474)
![{\displaystyle q\in C^{1}[a,b]\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1eb6e01010a11d964a63b3bf79d620077625bb83)
![{\displaystyle [x_{i},x_{i+1}]\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/022b4375c1548cc0bbbf2b262948b49d8956f798)
