Problem 5a
edit
State Newton's method for the approximate solution of
f ( x ) = 0 {\displaystyle f(x)=0\!\,} f ( x ) {\displaystyle f(x)\!\,} x {\displaystyle x\!\,}
Solution 5a
edit
x k + 1 = x k − f ( x k ) f ′ ( x k ) {\displaystyle x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}\!\,}
Problem 5b
edit
State and prove a convergence result for the method.
Solution 5b
edit
x k + 1 = x k − f ′ ( x k ) − 1 f ( x k ) x k + 1 − x ∗ ⏟ e k + 1 = x k − x ∗ ⏟ e k − f ′ ( x k ) − 1 f ( x k ) = f ′ ( x k ) − 1 [ f ′ ( x k ) e k − ( f ( x k ) − f ( x ∗ ) ⏟ 0 ) ) = f ′ ( x k ) − 1 [ f ′ ( x k ) e k − e k ∫ 0 1 f ′ ( s x k + ( 1 − s ) x ∗ ) d s ] = f ′ ( x k ) − 1 [ f ′ ( x k ) e k − f ′ ( x ∗ ) e k − e k ∫ 0 1 ( f ′ ( s x k + ( 1 − s ) x ∗ ) − f ′ ( x ∗ ) ) d s ] ‖ e k + 1 ‖ ≤ ‖ f ′ ( x k ) − 1 ‖ [ L ‖ e k ‖ 2 + L 2 ‖ e k ‖ 2 ] where L is Lipschitz constant of f ′ = ‖ f ′ ( x k ) − 1 ‖ 3 2 L ‖ e k ‖ 2 {\displaystyle {\begin{aligned}x_{k+1}&=x_{k}-f'(x_{k})^{-1}f(x_{k})\\\underbrace {x_{k+1}-x_{*}} _{e_{k+1}}&=\underbrace {x_{k}-x_{*}} _{e_{k}}-f'(x_{k})^{-1}f(x_{k})\\&=f'(x_{k})^{-1}[f'(x_{k})e_{k}-(f(x_{k})-\underbrace {f(x_{*})} _{0}))\\&=f'(x_{k})^{-1}\left[f'(x_{k})e_{k}-e_{k}\int _{0}^{1}f'(sx_{k}+(1-s)x_{*})ds\right]\\&=f'(x_{k})^{-1}\left[f'(x_{k})e_{k}-f'(x_{*})e_{k}-e_{k}\int _{0}^{1}(f'(sx_{k}+(1-s)x_{*})-f'(x_{*}))ds\right]\\\|e_{k+1}\|&\leq \|f'(x_{k})^{-1}\|\left[L\|e_{k}\|^{2}+{\frac {L}{2}}\|e_{k}\|^{2}\right]{\mbox{ where L is Lipschitz constant of }}f'\\&=\|f'(x_{k})^{-1}\|{\frac {3}{2}}L\|e_{k}\|^{2}\end{aligned}}\!\,}
Problem 5c
edit
What is the typical order of convergence? Are there situations in which the order of convergence is higher? Explain your answers to these questions.
Solution 5c
edit
The typical order of local convergence is quadratic.
x k + 1 = x k − f ( x k ) f ′ ( x k ) ⏟ g ( x k ) {\displaystyle x_{k+1}=\underbrace {x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}} _{g(x_{k})}\!\,}
g ′ ( x k ) = 1 − f ′ ( x k ) 2 − f ′ ( x k ) f ( x k ) f ′ ( x k ) 2 {\displaystyle g'(x_{k})=1-{\frac {f'(x_{k})^{2}-f'(x_{k})f(x_{k})}{f'(x_{k})^{2}}}\!\,}
g ′ ( x ∗ ) = 0 {\displaystyle g'(x_{*})=0\!\,}
g ( x k ) {\displaystyle g(x_{k})\!\,} x ∗ {\displaystyle x_{*}\!\,}
g ( x k ) ⏟ x k + 1 = g ( x ∗ ) ⏟ x ∗ + g ′ ( x ∗ ) ⏟ 0 e k + g ″ ( x ∗ ) 2 e k 2 + g ‴ ( ξ ) 6 e k 3 {\displaystyle \underbrace {g(x_{k})} _{x_{k+1}}=\underbrace {g(x_{*})} _{x_{*}}+\underbrace {g'(x_{*})} _{0}e_{k}+{\frac {g''(x_{*})}{2}}e_{k}^{2}+{\frac {g'''(\xi )}{6}}e_{k}^{3}\!\,}
g ″ ( x ∗ ) = 0 {\displaystyle g''(x_{*})=0\!\,}
Problem 6
edit
{ − u ″ ( x ) + u ( x ) = f ( x ) , 0 ≤ x ≤ 1 u ′ ( 0 ) = 2 , u ( 1 ) = 0 ( 1 ) {\displaystyle {\begin{cases}-u''(x)+u(x)=f(x),0\leq x\leq 1\\u'(0)=2,u(1)=0\end{cases}}\qquad (1)\!\,}
Problem 6a
edit
Derive a variational formulation for (1).
Solution 6a
edit
Find u ∈ H {\displaystyle u\in H\!\,} v ∈ H = { v ∈ H 1 [ 0 , 1 ] : v ( 1 ) = 0 } {\displaystyle v\in H=\{v\in H^{1}[0,1]:v(1)=0\}\!\,}
∫ 0 1 u ′ v ′ d x + ∫ 0 1 u v ⏟ a ( u , v ) = ∫ 0 1 f v − 2 v ( 0 ) ⏟ f ( v ) {\displaystyle \underbrace {\int _{0}^{1}u'v'dx+\int _{0}^{1}uv} _{a(u,v)}=\underbrace {\int _{0}^{1}fv-2v(0)} _{f(v)}\!\,}
Problem 6b
edit
What do we mean by Finite Element Approximation u h {\displaystyle u_{h}\!\,} u {\displaystyle u\!\,}
Solution 6b
edit
Let P = { x i } i = 0 N {\displaystyle P=\{x_{i}\}_{i=0}^{N}\!\,} [ 0 , 1 ] {\displaystyle [0,1]\!\,} V h {\displaystyle V_{h}\!\,} { ϕ i } i = 0 N {\displaystyle \{\phi _{i}\}_{i=0}^{N}\!\,}
u h = ∑ i = 0 N u h i ϕ i {\displaystyle u_{h}=\sum _{i=0}^{N}u_{hi}\phi _{i}\!\,}
u h i {\displaystyle u_{hi}\!\,}
j = 0 , 1 , … , N {\displaystyle j=0,1,\ldots ,N\!\,}
∑ i = 0 N u h i ∫ 0 1 ϕ i ′ ϕ j ′ d x + ∑ i = 0 N u h i ∫ 0 1 ϕ i ϕ j d x = ∫ 0 1 f ϕ j − 2 ϕ j ( 0 ) {\displaystyle \sum _{i=0}^{N}u_{hi}\int _{0}^{1}\phi _{i}'\phi _{j}'dx+\sum _{i=0}^{N}u_{hi}\int _{0}^{1}\phi _{i}\phi _{j}dx=\int _{0}^{1}f\phi _{j}-2\phi _{j}(0)\!\,}
Problem 6c
edit
State and prove an estimate for
‖ u − u h ‖ 1 ≡ ( ∫ 0 1 | u ( x ) − u h ( x ) | 2 d x + ∫ 0 1 | u ′ ( x ) − u h ′ ( x ) | 2 d x ) 1 2 {\displaystyle \|u-u_{h}\|_{1}\equiv \left(\int _{0}^{1}|u(x)-u_{h}(x)|^{2}dx+\int _{0}^{1}|u'(x)-u_{h}'(x)|^{2}dx\right)^{\frac {1}{2}}\!\,}
Solution 6c
edit
Cea's Lemma:
‖ u − u h ‖ 1 ≤ inf v ∈ V h C ‖ u − v ‖ 1 {\displaystyle \|u-u_{h}\|_{1}\leq \inf _{v\in V_{h}}C\|u-v\|_{1}\!\,}
v I {\displaystyle v_{I}\!\,} u {\displaystyle u\!\,}
‖ u − u h ‖ ≤ C ‖ u ″ ‖ ∞ h {\displaystyle \|u-u_{h}\|\leq C\|u''\|_{\infty }h\!\,}
Alternative Solution 6c
edit
Let { x k } 0 n {\displaystyle \{x_{k}\}_{0}^{n}} [ 0 , 1 ] {\displaystyle [0,1]} h {\displaystyle h}
∫ x k x k + 1 | u ( x ) − u h ( x ) | 2 d x {\displaystyle \int _{x_{k}}^{x_{k+1}}|u(x)-u_{h}(x)|^{2}dx}
For some ξ k ∈ [ x k , x k + 1 ] {\displaystyle \xi _{k}\in [x_{k},x_{k+1}]} u ( x ) − u h ( x ) = u ′ ( ξ k ) ∗ h {\displaystyle u(x)-u_{h}(x)=u'(\xi _{k})*h} u h {\displaystyle u_{h}}
∫ x k x k + 1 | u ( x ) − u h ( x ) | 2 d x = ∫ x k x k + 1 h 2 u ′ ( ξ k ) 2 d x = h 3 u ′ ( ξ k ) 2 ≤ h 3 | | u ′ | | ∞ {\displaystyle \int _{x_{k}}^{x_{k+1}}|u(x)-u_{h}(x)|^{2}dx=\int _{x_{k}}^{x_{k+1}}h^{2}u'(\xi _{k})^{2}dx=h^{3}u'(\xi _{k})^{2}\leq h^{3}||u'||_{\infty }}
Similarly, we can bound the L 2 ( x k , x k + h ) {\displaystyle L_{2}(x_{k},x_{k}+h)} h 3 | | u ″ | | ∞ {\displaystyle h^{3}||u''||_{\infty }} n = 1 / h {\displaystyle n=1/h}
| | u − u h ‖ | 2 ≤ 2 n h 3 max ( | | u ′ | | ∞ 2 , | | u ″ | | ∞ 2 ) = 2 h 2 max ( | | u ′ | | ∞ 2 , | | u ″ | | ∞ 2 ) . {\displaystyle \ ||u-u_{h}\||^{2}\leq 2nh^{3}\max(||u'||_{\infty }^{2},||u''||_{\infty }^{2})=2h^{2}\max(||u'||_{\infty }^{2},||u''||_{\infty }^{2}).}
Problem 6d
edit
Prove the formula
‖ u − u h ‖ 1 2 = ‖ u ‖ 1 2 − ‖ u h ‖ 1 2 {\displaystyle \|u-u_{h}\|_{1}^{2}=\|u\|_{1}^{2}-\|u_{h}\|_{1}^{2}\!\,}
Solution 6d
edit
a ( u − u h , u − u h ) ⏟ ‖ u − u h ‖ 1 2 + 2 a ( u − u h , u h ) ⏟ 0 = a ( u , u ) − 2 a ( u , u h ) + a ( u h , u h ) + 2 a ( u , u h ) − 2 a ( u h , u h ) = a ( u , u ) − a ( u h , u h ) = ‖ u ‖ 1 2 − ‖ u h ‖ 1 2 {\displaystyle {\begin{aligned}\underbrace {a(u-u_{h},u-u_{h})} _{\|u-u_{h}\|_{1}^{2}}+2\underbrace {a(u-u_{h},u_{h})} _{0}&=a(u,u)-2a(u,u_{h})+a(u_{h},u_{h})+2a(u,u_{h})-2a(u_{h},u_{h})\\&=a(u,u)-a(u_{h},u_{h})\\&=\|u\|_{1}^{2}-\|u_{h}\|_{1}^{2}\end{aligned}}\!\,}
Problem 7
edit
Consider the initial value problem
y ′ = f ( t , y ) , y ( t 0 ) = y 0 {\displaystyle y'=f(t,y),\quad y(t_{0})=y_{0}\!\,} f {\displaystyle f\!\,}
| f ( t , y ) − f ( t , z ) | ≤ L | y − z | {\displaystyle |f(t,y)-f(t,z)|\leq L|y-z|\!\,} t , y , z {\displaystyle t,y,z\!\,}
y n + 1 = y n − 1 + 2 h f ( t n , y n ) {\displaystyle y_{n+1}=y_{n-1}+2hf(t_{n},y_{n})\!\,} h {\displaystyle h\!\,} y n ≈ y ( t n ) {\displaystyle y_{n}\approx y(t_{n})\!\,} t n = t 0 + n h {\displaystyle t_{n}=t_{0}+nh\!\,} y 0 {\displaystyle y_{0}\!\,} y 1 {\displaystyle y_{1}\!\,}
Problem 7a
edit
Suppose the problem is posed on a finite interval t 0 ≤ t ≤ b {\displaystyle t_{0}\leq t\leq b\!\,} h = ( b − t 0 ) M {\displaystyle h={\frac {(b-t_{0})}{M}}\!\,} y 0 ^ {\displaystyle {\hat {y_{0}}}\!\,} y 1 ^ {\displaystyle {\hat {y_{1}}}\!\,}
| y 0 − y 0 ^ | ≤ ϵ , | y 1 − y 1 ^ | ≤ ϵ {\displaystyle |y_{0}-{\hat {y_{0}}}|\leq \epsilon ,\quad |y_{1}-{\hat {y_{1}}}|\leq \epsilon \!\,} C {\displaystyle C\!\,} h {\displaystyle h\!\,}
| y n − y n ^ | ≤ C ϵ {\displaystyle |y_{n}-{\hat {y_{n}}}|\leq C\epsilon \!\,} 0 ≤ n ≤ M {\displaystyle 0\leq n\leq M\!\,}
Solution 7a
edit
y n + 1 = y n − 1 + 2 h f ( t n , y n ) y ^ n + 1 = y ^ n − 1 + 2 h f ( t n , y ^ n ) {\displaystyle {\begin{aligned}y_{n+1}&=y_{n-1}+2hf(t_{n},y_{n})\\{\hat {y}}_{n+1}&={\hat {y}}_{n-1}+2hf(t_{n},{\hat {y}}_{n})\end{aligned}}}
e n ≡ y n − y ^ n {\displaystyle e_{n}\equiv y_{n}-{\hat {y}}_{n}\!\,}
e n + 1 ≤ e n − 1 + 2 h L e n ≤ ( 1 + 2 h L ) max { e n , e n − 1 } {\displaystyle {\begin{aligned}e_{n+1}&\leq e_{n-1}+2hLe_{n}\\&\leq (1+2hL)\max\{e_{n},e_{n-1}\}\end{aligned}}\!\,}
e n ≤ ( 1 + 2 h L ) n − 1 ϵ ≤ ( 1 + 2 h L ) n ϵ ≤ e 2 L h n ϵ ≤ e 2 L ( t n − t 0 ) ϵ {\displaystyle {\begin{aligned}e_{n}&\leq (1+2hL)^{n-1}\epsilon \\&\leq (1+2hL)^{n}\epsilon \\&\leq e^{2Lhn}\epsilon \\&\leq e^{2L(t_{n}-t_{0})}\epsilon \end{aligned}}\!\,}
Problem 7b
edit
Solution 7b
edit
Substituting into the midpoint rule we have,
y n + 1 = y n − 1 + 2 h λ y n {\displaystyle y_{n+1}=y_{n-1}+2h\lambda y_{n}\!\,}
y n + 1 − 2 h λ y n − y n − 1 = 0 {\displaystyle y_{n+1}-2h\lambda y_{n}-y_{n-1}=0\!\,}
y n = C 1 z 1 n + C 2 z 2 n {\displaystyle y_{n}=C_{1}z_{1}^{n}+C_{2}z_{2}^{n}\!\,}
z 1 , z 2 {\displaystyle z_{1},z_{2}\!\,}
z 2 − 2 h λ z − 1 {\displaystyle z^{2}-2h\lambda z-1\!\,}
z = h λ ( 1 ± 1 + 4 4 h 2 λ 2 ) {\displaystyle z=h\lambda \left(1\pm {\sqrt {1+{\frac {4}{4h^{2}\lambda ^{2}}}}}\right)\!\,}
λ {\displaystyle \lambda \!\,} y n → ∞ {\displaystyle y_{n}\rightarrow \infty \!\,} n → ∞ {\displaystyle n\rightarrow \infty \!\,} y ( t ) = e λ t {\displaystyle y(t)=e^{\lambda t}\!\,}
![{\displaystyle {\begin{aligned}x_{k+1}&=x_{k}-f'(x_{k})^{-1}f(x_{k})\\\underbrace {x_{k+1}-x_{*}} _{e_{k+1}}&=\underbrace {x_{k}-x_{*}} _{e_{k}}-f'(x_{k})^{-1}f(x_{k})\\&=f'(x_{k})^{-1}[f'(x_{k})e_{k}-(f(x_{k})-\underbrace {f(x_{*})} _{0}))\\&=f'(x_{k})^{-1}\left[f'(x_{k})e_{k}-e_{k}\int _{0}^{1}f'(sx_{k}+(1-s)x_{*})ds\right]\\&=f'(x_{k})^{-1}\left[f'(x_{k})e_{k}-f'(x_{*})e_{k}-e_{k}\int _{0}^{1}(f'(sx_{k}+(1-s)x_{*})-f'(x_{*}))ds\right]\\\|e_{k+1}\|&\leq \|f'(x_{k})^{-1}\|\left[L\|e_{k}\|^{2}+{\frac {L}{2}}\|e_{k}\|^{2}\right]{\mbox{ where L is Lipschitz constant of }}f'\\&=\|f'(x_{k})^{-1}\|{\frac {3}{2}}L\|e_{k}\|^{2}\end{aligned}}\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5f6f55b65fc3eadd56e58a8d680e56788e7c6137)
![{\displaystyle v\in H=\{v\in H^{1}[0,1]:v(1)=0\}\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/944b769d3268a571131ca656ea7fcf2dc14a0085)
![{\displaystyle [0,1]\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b26fc5fee30dada6f15cc080115cae582606d7f3)
![{\displaystyle [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/738f7d23bb2d9642bab520020873cccbef49768d)
![{\displaystyle \xi _{k}\in [x_{k},x_{k+1}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba08c76abca76c84c6a51368615f33f4430cc2)
