Explain the Eudoxos method in terms of the power method.
The iteration can be represented in matrix formulation as follows:
x
n
+
1
=
x
n
+
y
n
y
n
+
1
=
x
n
+
1
+
x
n
=
2
x
n
+
y
n
{\displaystyle {\begin{aligned}x_{n+1}&=x_{n}+y_{n}\\y_{n+1}&=x_{n+1}+x_{n}=2x_{n}+y_{n}\end{aligned}}\!\,}
[
1
1
2
1
]
⏟
A
[
x
n
y
n
]
=
[
x
n
+
1
y
n
+
1
]
{\displaystyle \underbrace {\begin{bmatrix}1&1\\2&1\end{bmatrix}} _{A}{\begin{bmatrix}x_{n}\\y_{n}\end{bmatrix}}={\begin{bmatrix}x_{n+1}\\y_{n+1}\end{bmatrix}}\!\,}
A
{\displaystyle A\!\,}
A
{\displaystyle A\!\,}
1
±
2
{\displaystyle 1\pm {\sqrt {2}}\!\,}
1
+
2
{\displaystyle 1+{\sqrt {2}}\!\,}
[
2
2
]
{\displaystyle {\begin{bmatrix}{\sqrt {2}}\\2\end{bmatrix}}\!\,}
y
n
/
x
n
→
2
{\displaystyle y_{n}/x_{n}\rightarrow {\sqrt {2}}\!\,}
How many iterations are required for an error
|
y
n
/
x
n
−
2
|
≤
10
−
6
{\displaystyle |y_{n}/x_{n}-{\sqrt {2}}|\leq 10^{-6}\!\,}
Since convergence is linear, 7 steps is required to achieve the error bound.
Let
{
p
n
(
x
)
}
{\displaystyle \{p_{n}(x)\}\!\,}
[
a
,
b
]
{\displaystyle [a,b]\!\,}
w
(
x
)
{\displaystyle w(x)\!\,}
p
n
{\displaystyle p_{n}\!\,}
n
{\displaystyle n\!\,}
p
n
{\displaystyle p_{n}\!\,}
p
n
(
x
)
=
(
x
−
a
n
)
p
n
−
1
(
x
)
−
b
n
p
n
−
2
(
x
)
{\displaystyle p_{n}(x)=(x-a_{n})p_{n-1}(x)-b_{n}p_{n-2}(x)\!\,}
a
n
{\displaystyle a_{n}\!\,}
b
n
{\displaystyle b_{n}\!\,}
First notice that
p
n
−
x
p
n
−
1
∈
Π
n
−
1
{\displaystyle p_{n}-xp_{n-1}\in \Pi ^{n-1}\!\,}
n
−
1
{\displaystyle n-1\!\,}
p
n
−
x
p
n
−
1
=
−
a
n
p
n
−
1
−
b
n
p
n
−
2
+
∑
i
=
0
n
−
3
α
i
p
i
(
∗
)
{\displaystyle p_{n}-xp_{n-1}=-a_{n}p_{n-1}-b_{n}p_{n-2}+\sum _{i=0}^{n-3}\alpha _{i}p_{i}\qquad (*)\!\,}
(
∗
)
{\displaystyle (*)\!\,}
p
n
−
1
{\displaystyle p_{n-1}\!\,}
−
⟨
x
p
n
−
1
,
p
n
−
1
⟩
=
−
a
n
⟨
p
n
−
1
,
p
n
−
1
⟩
{\displaystyle -\langle xp_{n-1},p_{n-1}\rangle =-a_{n}\langle p_{n-1},p_{n-1}\rangle \!\,}
a
n
=
⟨
x
p
n
−
1
,
p
n
−
1
⟩
⟨
p
n
−
1
,
p
n
−
1
⟩
{\displaystyle a_{n}={\frac {\langle xp_{n-1},p_{n-1}\rangle }{\langle p_{n-1},p_{n-1}\rangle }}\!\,}
(
∗
)
{\displaystyle (*)\!\,}
p
n
−
2
{\displaystyle p_{n-2}\!\,}
b
n
=
⟨
x
p
n
−
1
,
p
n
−
2
⟩
⟨
p
n
−
2
,
p
n
−
2
⟩
{\displaystyle b_{n}={\frac {\langle xp_{n-1},p_{n-2}\rangle }{\langle p_{n-2},p_{n-2}\rangle }}\!\,}
⟨
x
p
n
−
1
,
p
n
−
2
⟩
=
⟨
p
n
−
1
,
x
p
n
−
2
⟩
=
⟨
p
n
−
1
,
p
n
−
1
+
∑
i
=
0
n
−
2
α
i
p
i
⟩
=
⟨
p
n
−
1
,
p
n
−
1
⟩
{\displaystyle {\begin{aligned}\langle xp_{n-1},p_{n-2}\rangle &=\langle p_{n-1},xp_{n-2}\rangle \\&=\langle p_{n-1},p_{n-1}+\sum _{i=0}^{n-2}\alpha _{i}p_{i}\rangle \\&=\langle p_{n-1},p_{n-1}\rangle \end{aligned}}\!\,}
b
n
=
⟨
p
n
−
1
,
p
n
−
1
⟩
⟨
p
n
−
2
,
p
n
−
2
⟩
{\displaystyle b_{n}={\frac {\langle p_{n-1},p_{n-1}\rangle }{\langle p_{n-2},p_{n-2}\rangle }}\!\,}
(
∗
)
{\displaystyle (*)\!\,}
p
k
,
k
=
0
,
…
,
n
−
3
{\displaystyle p_{k},k=0,\ldots ,n-3\!\,}
α
k
=
−
⟨
x
p
n
−
1
,
p
k
⟩
⟨
p
k
,
p
k
⟩
{\displaystyle \alpha _{k}=-{\frac {\langle xp_{n-1},p_{k}\rangle }{\langle p_{k},p_{k}\rangle }}\!\,}
⟨
x
p
n
−
1
,
p
k
⟩
=
⟨
p
n
−
1
,
x
p
k
⏟
∈
Π
n
−
2
⟩
=
0
{\displaystyle \langle xp_{n-1},p_{k}\rangle =\langle p_{n-1},\underbrace {xp_{k}} _{\in \Pi ^{n-2}}\rangle =0\!\,}
α
k
=
0
{\displaystyle \alpha _{k}=0\!\,}
k
=
0
,
1
…
,
n
−
3
{\displaystyle k=0,1\ldots ,n-3\!\,}
Find
{
p
0
,
p
1
,
p
2
}
{\displaystyle \{p_{0},p_{1},p_{2}\}\!\,}
p
i
{\displaystyle p_{i}\!\,}
i
{\displaystyle i\!\,}
[
0
,
∞
)
{\displaystyle [0,\infty )\!\,}
w
(
x
)
=
e
−
x
{\displaystyle w(x)=e^{-x}\!\,}
Using Gram Schmidt with inner product defined as
⟨
f
,
g
⟩
=
∫
0
∞
w
(
x
)
f
g
d
x
{\displaystyle \langle f,g\rangle =\int _{0}^{\infty }w(x)fgdx\!\,}
1
,
x
,
x
2
{\displaystyle 1,x,x^{2}\!\,}
p
0
=
1
{\displaystyle p_{0}=1\!\,}
p
1
=
x
−
1
{\displaystyle p_{1}=x-1\!\,}
p
2
=
x
2
−
4
x
+
2
{\displaystyle p_{2}=x^{2}-4x+2\!\,}
Find the weights and nodes of the 2 point Gaussian formula
∫
0
∞
f
(
x
)
e
−
x
d
x
≈
w
1
f
(
x
1
)
+
w
2
f
(
x
2
)
{\displaystyle \int _{0}^{\infty }f(x)e^{-x}dx\approx w_{1}f(x_{1})+w_{2}f(x_{2})\!\,}
∫
0
∞
x
n
e
−
x
d
x
=
n
!
,
0
!
=
1
{\displaystyle \int _{0}^{\infty }x^{n}e^{-x}dx=n!,\quad 0!=1\!\,}
Using test functions
f
(
x
)
=
1
{\displaystyle f(x)=1\!\,}
f
(
x
)
=
x
{\displaystyle f(x)=x\!\,}
p
2
{\displaystyle p_{2}\!\,}
x
1
=
2
+
2
{\displaystyle x_{1}=2+{\sqrt {2}}\!\,}
x
2
=
2
−
2
{\displaystyle x_{2}=2-{\sqrt {2}}\!\,}
w
1
=
2
−
2
4
{\displaystyle w_{1}={\frac {2-{\sqrt {2}}}{4}}\!\,}
w
2
=
2
+
2
4
{\displaystyle w_{2}={\frac {2+{\sqrt {2}}}{4}}\!\,}
![{\displaystyle [a,b]\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1ef1354dbfeea71ab05cf297ffc40786b7813474)
