== Problem 1 == == Problem 1a == == Solution 1a == We wish to show that ‖ b − A x ( c ) ‖ = ‖ ν e 1 − H k c ‖ {\displaystyle \,\!\|b-Ax(c)\|=\|\nu e_{1}-H_{k}c\|} ‖ b − A x ( c ) ‖ = ‖ b − A ( x 0 + V k c ) ‖ = ‖ b − A x 0 − A V k c ‖ = ‖ r 0 − A V k c ‖ = ‖ r 0 − V k + 1 H k c ‖ = ‖ ν v 1 − V k + 1 H k c ‖ = ‖ V k + 1 ( ν e 1 − H k c ) ⏟ h c ‖ = ( V k + 1 h c , V k + 1 h c ) 1 2 = ( ( V k + 1 h c ) T V k + 1 h c ) 1 2 = ( h c T V k + 1 T V k + 1 h c ) 1 2 = ( h c T h c ) 1 2 = ‖ h c ‖ = ‖ ν e 1 − H k c ‖ {\displaystyle {\begin{aligned}\|b-Ax(c)\|&=\|b-A(x_{0}+V_{k}c)\|\\&=\|b-Ax_{0}-AV_{k}c\|\\&=\|r_{0}-AV_{k}c\|\\&=\|r_{0}-V_{k+1}H_{k}c\|\\&=\|\nu v_{1}-V_{k+1}H_{k}c\|\\&=\|V_{k+1}\underbrace {(\nu e_{1}-H_{k}c)} _{h_{c}}\|\\&=(V_{k+1}h_{c},V_{k+1}h_{c})^{\frac {1}{2}}\\&=((V_{k+1}h_{c})^{T}V_{k+1}h_{c})^{\frac {1}{2}}\\&=(h_{c}^{T}V_{k+1}^{T}V_{k+1}h_{c})^{\frac {1}{2}}\\&=(h_{c}^{T}h_{c})^{\frac {1}{2}}\\&=\|h_{c}\|\\&=\|\nu e_{1}-H_{k}c\|\end{aligned}}} == Problem 1b == == Solution 1b == We would like to transform H k {\displaystyle H_{k}\!\,} , a ( k + 1 ) × k {\displaystyle (k+1)\times k\!\,} upper Hessenberg matrix, into QR form. The cost is on the order of 4 k 2 + 1 2 k 2 = 4.5 k 2 {\displaystyle 4k^{2}+{\frac {1}{2}}k^{2}=4.5k^{2}} from the cost of Given's Rotations and backsolving. === Given's Rotations Cost === We need k {\displaystyle k\!\,} Given's Rotation multiplies to zero out each of the k {\displaystyle k\!\,} subdiagonal entries and hence transform H k {\displaystyle H_{k}\!\,} into upper triangular form R {\displaystyle R\!\,} , Each successive Given's Rotations multiply on an upper Hessenberg matrix requires four fewer multiplies because each previous subdiagonal entry has been zeroed out by a Given's Rotation multiply. Hence the cost of k {\displaystyle k\!\,} Given's Rotations multiplies is 4 k + 4 ( k − 1 ) + … + 4 ⋅ 1 < 4 k ⋅ k = 4 k 2 {\displaystyle 4k+4(k-1)+\ldots +4\cdot 1<4k\cdot k=4k^{2}} === Back Solving Cost === R {\displaystyle R\!\,} is a ( k + 1 ) × k {\displaystyle (k+1)\times k\!\,} upper triangular matrix with last row zero. Hence, we need to backsolve k {\displaystyle k\!\,} upper triangular rows. 1 + 2 + … + k = k ( k + 1 ) 2 = k 2 2 + k 2 {\displaystyle 1+2+\ldots +k={\frac {k(k+1)}{2}}={\frac {k^{2}}{2}}+{\frac {k}{2}}} == Problem 2 == == Problem 2a == == Solution 2a == The composite trapezoidal rule is Q T , n ( f ) = h 2 ( f ( a ) + f ( b ) ) + h ∑ k = 1 n − 1 f ( x k ) {\displaystyle Q_{T,n}(f)={\frac {h}{2}}(f(a)+f(b))+h\sum _{k=1}^{n-1}f(x_{k})\!\,} The error is I ( f ) − Q T , n ( f ) = − ( b − a ) f ′ ′ ( ξ ) 12 h 2 {\displaystyle I(f)-Q_{T,n}(f)=-{\frac {(b-a)f^{\prime \prime }(\xi )}{12}}h^{2}} where ξ ∈ [ a , b ] {\displaystyle \xi \in [a,b]\!\,} . === Derivation of Composite Trapezoidal Error === The local error, the error on one interval, is − h 3 12 f ′ ′ ( η ) {\displaystyle -{\frac {h^{3}}{12}}f^{\prime \prime }(\eta )\!\,} .Observe that n min η ∈ [ a , b ] f ′ ′ ( η i ) ≤ ∑ i = 1 n f ′ ′ ( η i ) ≤ n max η ∈ [ a , b ] f ′ ′ ( η i ) {\displaystyle n\min _{\eta \in [a,b]}f^{\prime \prime }(\eta _{i})\leq \sum _{i=1}^{n}f^{\prime \prime }(\eta _{i})\leq n\max _{\eta \in [a,b]}f^{\prime \prime }(\eta _{i})\!\,} which implies min η ∈ [ a , b ] f ′ ′ ( η i ) ≤ ∑ i = 1 n f ′ ′ ( η i ) n ≤ max η ∈ [ a , b ] f ′ ′ ( η i ) {\displaystyle \min _{\eta \in [a,b]}f^{\prime \prime }(\eta _{i})\leq \sum _{i=1}^{n}{\frac {f^{\prime \prime }(\eta _{i})}{n}}\leq \max _{\eta \in [a,b]}f^{\prime \prime }(\eta _{i})\!\,} Hence, the Intermediate Value Theorem implies there exists a ξ ∈ [ a , b ] {\displaystyle \xi \in [a,b]\!\,} such that f ′ ′ ( ξ ) = ∑ i = 1 n f ′ ′ ( η i ) n {\displaystyle f^{\prime \prime }(\xi )=\sum _{i=1}^{n}{\frac {f^{\prime \prime }(\eta _{i})}{n}}\!\,} .Multiplying both sides of the equation by n {\displaystyle n\!\,} , n f ′ ′ ( ξ ) = ∑ i = 1 n f ′ ′ ( η i ) {\displaystyle nf^{\prime \prime }(\xi )=\sum _{i=1}^{n}f^{\prime \prime }(\eta _{i})\!\,} Using this relationship, we have I ( f ) − Q T , n ( f ) = ∑ i = 1 n I i ( f ) − Q i ( f ) = ∑ i = 1 n [ − h 3 12 f ′ ′ ( η i ) ] = − h 3 12 f ′ ′ ( ξ ) n = − h 3 12 f ′ ′ ( ξ ) ( b − a h ) = − h 2 12 f ′ ′ ( ξ ) ( b − a ) {\displaystyle {\begin{aligned}I(f)-Q_{T,n}(f)&=\sum _{i=1}^{n}I_{i}(f)-Q_{i}(f)\\&=\sum _{i=1}^{n}\left[-{\frac {h^{3}}{12}}f^{\prime \prime }(\eta _{i})\right]\\&=-{\frac {h^{3}}{12}}f^{\prime \prime }(\xi )n\\&=-{\frac {h^{3}}{12}}f^{\prime \prime }(\xi )({\frac {b-a}{h}})\\&=-{\frac {h^{2}}{12}}f^{\prime \prime }(\xi )(b-a)\end{aligned}}} === Derivation of Local Error === The error in polynomial interpolation can be found by using the following theorem: Assume f n + 1 {\displaystyle f^{n+1}\!\,} exists on [ a , b ] {\displaystyle [a,b]\!\,} and { x 0 , x 1 , … , x n | x ∈ [ a , b ] } . {\displaystyle \{x_{0},x_{1},\ldots ,x_{n}|x\in [a,b]\}.\!\,} P n {\displaystyle P_{n}\!\,} interpolates f {\displaystyle f\!\,} at { x j } j = 0 n {\displaystyle \{x_{j}\}_{j=0}^{n}\!\,} . Then there is a ξ x {\displaystyle \xi _{x}\!\,} ( ξ {\displaystyle \xi \!\,} is dependent on x {\displaystyle x\!\,} ) such that f ( x ) − p n ( x ) = ( x − x 0 ) ( x − x 1 ) . . . ( x − x n ) ( n + 1 ) ! f ( n + 1 ) ( ξ x ) {\displaystyle f(x)-p_{n}(x)={\frac {(x-x_{0})(x-x_{1})...(x-x_{n})}{(n+1)!}}f^{(n+1)}(\xi _{x})\!\,} where ξ x {\displaystyle \xi _{x}\!\,} lies in ( m , M ) {\displaystyle (m,M)\!\,} , m = min { x 0 , x 1 , … , x n , X } {\displaystyle m=\min\{x_{0},x_{1},\ldots ,x_{n},X\}\!\,} , M = max { x 0 , x 1 , … , x n , X } {\displaystyle M=\max\{x_{0},x_{1},\ldots ,x_{n},X\}\!\,} Applying the theorem yields, f ( x ) − p 1 ( x ) = ( x − a ) ( x − b ) f ′ ′ ( ξ x ) 2 {\displaystyle f(x)-p_{1}(x)=(x-a)(x-b){\frac {f^{\prime \prime }(\xi _{x})}{2}}} Hence, E ( f ) = ∫ a b f ( x ) − p 1 ( x ) d x = ∫ a b ( x − a ) ⏟ > 0 ( x − b ) ⏟ < 0 ⏟ w ( x ) f ′ ′ ( ξ x ) 2 d x {\displaystyle {\begin{aligned}E(f)&=\int _{a}^{b}f(x)-p_{1}(x)dx\\&=\int _{a}^{b}\underbrace {\underbrace {(x-a)} _{>0}\underbrace {(x-b)} _{<0}} _{w(x)}{\frac {f^{\prime \prime }(\xi _{x})}{2}}dx\end{aligned}}} Since a {\displaystyle a\!\,} is the start of the interval, x − a {\displaystyle x-a\!\,} is always positive. Conversely, since b {\displaystyle b\!\,} is the end of the interval, x − b {\displaystyle x-b\!\,} is always negative. Hence, w ( x ) < 0 {\displaystyle w(x)<0\!\,} is always of one sign. Hence from the mean value theorem of integration, there exists a ζ ∈ [ a , b ] {\displaystyle \zeta \in [a,b]\!\,} such that E ( f ) = f ′ ′ ( ζ ) 2 ∫ a b ( x − a ) ( x − b ) d x {\displaystyle E(f)={\frac {f^{\prime \prime }(\zeta )}{2}}\int _{a}^{b}(x-a)(x-b)dx\!\,} Note that f ′ ′ ( ζ ) {\displaystyle f^{\prime \prime }(\zeta )} is a constant and does not depend on x {\displaystyle x\!\,} . Integrating ∫ a b ( x − a ) ( x − b ) d x {\displaystyle \int _{a}^{b}(x-a)(x-b)dx\!\,} , yields, E ( f ) = f ′ ′ ( ζ ) 2 ( − ( b − a ) 6 ) = − f ′ ′ ( ζ ) ( b − a ) 12 {\displaystyle {\begin{aligned}E(f)&={\frac {f^{\prime \prime }(\zeta )}{2}}\left(-{\frac {(b-a)}{6}}\right)\\&=-{\frac {f^{\prime \prime }(\zeta )(b-a)}{12}}\!\,\end{aligned}}} == Problem 2b == == Solution 2b == STOER AND BUESCH pg 162 INTRODUCTION TO APPLIED NUMERICAL ANALYSIS by RICHARD HAMMING pg 178 The error for the composite trapezoidal rule at n {\displaystyle n\!\,} points in [ a , b ] {\displaystyle [a,b]\!\,} is E n = I ( f ) − Q T , n = − ( b − a ) h 2 12 + O ( h 3 ) {\displaystyle E_{n}=I(f)-Q_{T,n}={\frac {-(b-a)h^{2}}{12}}+{\mathcal {O}}(h^{3})\!\,} With 2 n {\displaystyle 2n\!\,} points, there are twice as many intervals, but the intervals are half as wide. Hence, the error for the composite trapezoidal rule at 2 n {\displaystyle 2n\!\,} points in [ a , b ] {\displaystyle [a,b]\!\,} is E 2 n = I ( f ) − Q T , 2 n = 2 ⋅ − ( b − a ) ( h 2 ) 2 12 + O ( h 3 ) = − ( b − a ) h 2 24 + O ( h 3 ) {\displaystyle E_{2n}=I(f)-Q_{T,2n}=2\cdot {\frac {-(b-a)({\frac {h}{2}})^{2}}{12}}+{\mathcal {O}}(h^{3})={\frac {-(b-a)h^{2}}{24}}+{\mathcal {O}}(h^{3})\!\,} We can eliminate the h 2 {\displaystyle h^{2}\!\,} term by choosing using an appropriate linear combination of E n {\displaystyle E_{n}\!\,} and E 2 n {\displaystyle E_{2n}\!\,} . This gives a new error rule with h 3 {\displaystyle h^{3}\!\,} error. E n − 2 E 2 n = − ( b − a ) h 2 12 − 2 ⋅ − ( b − a ) h 2 24 + O ( h 3 ) = O ( h 3 ) {\displaystyle {\begin{aligned}E_{n}-2E_{2n}&={\frac {-(b-a)h^{2}}{12}}-2\cdot {\frac {-(b-a)h^{2}}{24}}+{\mathcal {O}}(h^{3})\\&={\mathcal {O}}(h^{3})\end{aligned}}} Substituting our equations for E n {\displaystyle E_{n}\!\,} and E 2 n {\displaystyle E_{2n}\!\,} on the left had side gives I ( f ) − Q T , n − 2 I ( f ) − 2 Q T , 2 n = O ( h 3 ) {\displaystyle I(f)-Q_{T,n}-2I(f)-2Q_{T,2n}={\mathcal {O}}(h^{3})\!\,} I ( f ) = 2 Q T , 2 n − Q T , n + O ( h 3 ) {\displaystyle I(f)=2Q_{T,2n}-Q_{T,n}+{\mathcal {O}}(h^{3})\!\,} If we call our new rule Q ^ {\displaystyle {\hat {Q}}\!\,} we have Q ^ = 2 Q T , 2 n − Q T , n {\displaystyle {\hat {Q}}=2Q_{T,2n}-Q_{T,n}\!\,} whose error is on the order of O ( h 3 ) {\displaystyle {\mathcal {O}}(h^{3})\!\,} == Problem 3 == == Problem 3a == == Solution 3a == Let A ~ k {\displaystyle {\tilde {A}}_{k}\!\,} be the σ k {\displaystyle \sigma _{k}\!\,} -shifted matrix of A k {\displaystyle A_{k}\!\,} i.e. A ~ k = A k − σ k I = [ a 11 − σ k a 12 a 21 a 22 − σ k ] , {\displaystyle {\tilde {A}}_{k}=A_{k}-\sigma _{k}I={\begin{bmatrix}a_{11}-\sigma _{k}&a_{12}\\a_{21}&a_{22}-\sigma _{k}\end{bmatrix}},} Q k T {\displaystyle Q_{k}^{T}\!\,} is an orthogonal 2x2 Given's rotations matrix. Q k T {\displaystyle Q_{k}^{T}\!\,} 's entries are chosen such that when Q k T {\displaystyle Q_{k}^{T}\!\,} is pre-multiplied against the 2x2 matrix A ~ k {\displaystyle {\tilde {A}}_{k}\!\,} , Q k T {\displaystyle Q_{k}^{T}\!\,} will zero out the (2,1) entry of A ~ k {\displaystyle {\tilde {A}}_{k}\!\,} and scale A ~ k {\displaystyle {\tilde {A}}_{k}\!\,} 's remaining three entries i.e. Q k T A ~ k = [ ∗ ∗ 0 ∗ ] = R k {\displaystyle Q_{k}^{T}{\tilde {A}}_{k}={\begin{bmatrix}*&*\\0&*\end{bmatrix}}=R_{k}} where ∗ {\displaystyle *\!\,} denotes calculable scalar values we are not interested in and R k {\displaystyle R_{k}\!\,} is our desired upper triangular matrix sought by the QR algorithm. Since Q k T {\displaystyle Q_{k}^{T}\!\,} is orthogonal, the above equation implies Q k T A ~ k = R k Q k Q k T A ~ k = Q k R k A ~ k = Q k R k {\displaystyle {\begin{aligned}Q_{k}^{T}{\tilde {A}}_{k}&=R_{k}\\Q_{k}Q_{k}^{T}{\tilde {A}}_{k}&=Q_{k}R_{k}\\{\tilde {A}}_{k}&=Q_{k}R_{k}\end{aligned}}} The Given's rotation Q k T {\displaystyle Q_{k}^{T}\!\,} is given by Q k T = [ c s − s c ] {\displaystyle Q_{k}^{T}={\begin{bmatrix}c&s\\-s&c\end{bmatrix}}} where c = a 11 − σ k r s = a 21 r r = ( a 11 − σ k ) 2 + a 21 2 {\displaystyle {\begin{aligned}c&={\frac {a_{11}-\sigma _{k}}{r}}\\s&={\frac {a_{21}}{r}}\\r&={\sqrt {(a_{11}-\sigma _{k})^{2}+a_{21}^{2}}}\end{aligned}}} Taking the transpose of Q k T {\displaystyle Q_{k}^{T}\!\,} yields Q k = [ c − s s c ] {\displaystyle Q_{k}={\begin{bmatrix}c&-s\\s&c\end{bmatrix}}} == Problem 3b == == Solution 3b == From hypothesis and part (a), A k + 1 = R k Q k + σ k I = [ ∗ ∗ 0 r 22 ] [ c − s s c ] + [ σ k 0 0 σ k ] {\displaystyle {\begin{aligned}A_{k+1}&=R_{k}Q_{k}+\sigma _{k}I\\&={\begin{bmatrix}*&*\\0&r_{22}\end{bmatrix}}{\begin{bmatrix}c&-s\\s&c\end{bmatrix}}+{\begin{bmatrix}\sigma _{k}&0\\0&\sigma _{k}\end{bmatrix}}\end{aligned}}} Let A k + 1 ( 2 , 1 ) {\displaystyle A_{k+1}(2,1)\!\,} be the (2,1) entry of A k {\displaystyle A_{k}\!\,} . Using the above equation, we can find A k + 1 ( 2 , 1 ) {\displaystyle A_{k+1}(2,1)\!\,} by finding the inner product of the second row of R k {\displaystyle R_{k}\!\,} and first column Q k {\displaystyle Q_{k}\!\,} and adding the (2,1) entry of σ k I {\displaystyle \sigma _{k}I\!\,} i.e. A k + 1 ( 2 , 1 ) = ( 0 ⋅ c + r 22 ⋅ s ) + 0 = r 22 s {\displaystyle {\begin{aligned}A_{k+1}(2,1)&=(0\cdot c+r_{22}\cdot s)+0\\&=r_{22}s\end{aligned}}} We need to find the value of r 22 {\displaystyle r_{22}\!\,} so we need to calculate R k {\displaystyle R_{k}\!\,} . From hypothesis and the orthogonality of Q k {\displaystyle Q_{k}\!\,} , we have A k − σ k I = Q k R k Q k T ( A k − σ k I ) = Q k T Q k R k Q k T ( A k − σ k I ) = R k R k = Q k T ( A k − σ k I ) = [ c s − s c ] [ a 11 − σ k a 12 δ a 22 − σ k ] {\displaystyle {\begin{aligned}A_{k}-\sigma _{k}I&=Q_{k}R_{k}\\Q_{k}^{T}(A_{k}-\sigma _{k}I)&=Q_{k}^{T}Q_{k}R_{k}\\Q_{k}^{T}(A_{k}-\sigma _{k}I)&=R_{k}\\R_{k}&=Q_{k}^{T}(A_{k}-\sigma _{k}I)\\&={\begin{bmatrix}c&s\\-s&c\end{bmatrix}}{\begin{bmatrix}a_{11}-\sigma _{k}&a_{12}\\\delta &a_{22}-\sigma _{k}\end{bmatrix}}\end{aligned}}} From R k {\displaystyle R_{k}\!\,} , we can find its (2,2) entry r 2 2 {\displaystyle r_{2}2\!\,} by using inner products. r 22 = − s ⋅ a 12 + c ⋅ ( a 22 − σ k ) {\displaystyle r_{22}=-s\cdot a_{12}+c\cdot (a_{22}-\sigma _{k})\!\,} Now that we have r 22 {\displaystyle r_{22}\!\,} we can calculate A k + 1 ( 2 , 1 ) {\displaystyle A_{k+1}(2,1)\!\,} by using appropriate substitutions A k + 1 ( 2 , 1 ) = r 22 ⋅ s = ( − s a 12 + c ( a 22 − σ k ) ) s = − s 2 a 12 + c s ( a 22 − σ k ) = − δ 2 a 12 ( a 11 − σ k ) 2 + δ 2 + ( a 11 − σ k ) ( a 22 − σ k ) δ ( a 11 − σ k ) 2 + δ 2 = − δ 2 a 12 + δ ( a 11 − σ k ) ( a 22 − σ k ) ( a 11 − σ k ) 2 + δ 2 ≈ − δ 2 a 12 + δ ( a 11 − σ k ) ( a 22 − σ k ) ( a 11 − σ k ) 2 {\displaystyle {\begin{aligned}A_{k+1}(2,1)&=r_{22}\cdot s\\&=(-sa_{12}+c(a_{22}-\sigma _{k}))s\\&=-s^{2}a_{12}+cs(a_{22}-\sigma _{k})\\&={\frac {-\delta ^{2}a_{12}}{(a_{11}-\sigma _{k})^{2}+\delta ^{2}}}+{\frac {(a_{11}-\sigma _{k})(a_{22}-\sigma _{k})\delta }{(a_{11}-\sigma _{k})^{2}+\delta ^{2}}}\\&={\frac {-\delta ^{2}a_{12}+\delta (a_{11}-\sigma _{k})(a_{22}-\sigma _{k})}{(a_{11}-\sigma _{k})^{2}+\delta ^{2}}}\\&\approx {\frac {-\delta ^{2}a_{12}+\delta (a_{11}-\sigma _{k})(a_{22}-\sigma _{k})}{(a_{11}-\sigma _{k})^{2}}}\end{aligned}}} since δ {\displaystyle \delta \!\,} is a small number. Let our shift σ k = a 22 {\displaystyle \sigma _{k}=a_{22}\!\,} . Then the above equation yields, A k + 1 ( 2 , 1 ) ≈ − δ 2 a 12 + δ ( a 11 − σ k ) ( a 22 − σ k ) ( a 11 − σ k ) 2 ≈ − δ 2 a 12 + δ ( a 11 − a 22 ) ( a 22 − a 22 ) ( a 11 − a 22 ) 2 = − δ 2 a 12 ( a 11 − a 22 ) 2 {\displaystyle {\begin{aligned}A_{k+1}(2,1)&\approx {\frac {-\delta ^{2}a_{12}+\delta (a_{11}-\sigma _{k})(a_{22}-\sigma _{k})}{(a_{11}-\sigma _{k})^{2}}}\\&\approx {\frac {-\delta ^{2}a_{12}+\delta (a_{11}-a_{22})(a_{22}-a_{22})}{(a_{11}-a_{22})^{2}}}\\&={\frac {-\delta ^{2}a_{12}}{(a_{11}-a_{22})^{2}}}\end{aligned}}} Hence, | A k + 1 ( 2 , 1 ) | ≈ | δ 2 a 12 ( a 11 − a 22 ) 2 | ≤ | δ 2 | {\displaystyle {\begin{aligned}|A_{k+1}(2,1)|&\approx \left|{\frac {\delta ^{2}a_{12}}{(a_{11}-a_{22})^{2}}}\right|\\&\leq |\delta ^{2}|\end{aligned}}} since | a 12 | ≤ ( a 11 − a 22 ) 2 {\displaystyle |a_{12}|\leq (a_{11}-a_{22})^{2}\!\,} Hence we have shown that A k + 1 ( 2 , 1 ) {\displaystyle A_{k+1}(2,1)\!\,} is of order δ 2 {\displaystyle \delta ^{2}\!\,} . If δ {\displaystyle \delta \!\,} is small, the QR convergence rate will be quadratic.