[<< wikibooks] Numerical Methods Qualification Exam Problems and Solutions (University of Maryland)/January 2008
== 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.