数学代写|Final Exam Numerical Analysis

Write down a table with short answers to the following questions. Below the table, include a brief justification/reasoning for your answer for each question (you will not get points without an explanation!).
(a) How many iterations does Newton’s method require to solve a linear equation?
(b) The 2-norm condition number of an $n \times n$ matrix with singular values $\sigma_{1} \geq$ $\sigma_{2} \cdots \geq \sigma_{n}$ is …
(c) (3 pts) To leading order, how many FLOPs are required to solve an $[n \times n]$ linear system if we already know the SVD decomposition/factorization of the matrix. For full points, give the constant in front of the leading order term.
(d) (3 pts) Using the initial guess $\mathrm{x}{0}=[0,1,0]^{T}$, the power method applied to the matrix $$ A=\left[\begin{array}{ccc} 4 & 0 & 0 \ 0 & -2 & 0 \ 0 & 0 & 1 \end{array}\right] $$ will converge to what eigenvalue if exact arithmetic (no roundoff error) is used? (e) For the nodes $x{0}=-1, x_{1}=0, x_{2}=1$, the Lagrange interpolation polynomial $L_{0}(x)$ corresponding to node $x_{0}$ is $\frac{1}{2} x^{2}-\frac{1}{2} x .$
(f) True or false: The $n+1$ point Lagrange polynomial
$$
p_{n}(x)=\sum_{k=0}^{n} \exp \left(x_{k}\right) L_{k}(x)+\sum_{k=0}^{n} L_{k}(x)
$$
interpolates the function $\exp (x)$.
(g) The Legendre polynomial of degree $n$ is orthogonal to every polynomial with degree $(n-1)$ or less.
(h) True or False: The three point Simpsons rule and the three point Gauss(Legendre) quadrature formulas are equally accurate approximations of
$$
\int_{-1}^{1}\left(x^{5}+1\right) d x
$$
(i) Let $I=\int_{a}^{b} f(x) d x$, and let $I_{n}$ be the result of the composite Simpson’s rule approximation to $I$ with $n+1$ quadrature points, and denote $e_{n}=\left|I-I_{n}\right|$. For $n$ large, what does $e_{2 n} / e_{n}$ converge to?

$[10=3+3+2+2$ pts $]$ Newton’s method computes the new iterate $x_{k+1}$ as the $x$ intercept of the “line of best fit” through the point $\left(x_{k}, f\left(x_{k}\right)\right)$, i.e., the line that passes through $\left(x_{k}, f\left(x_{k}\right)\right)$ and whose first derivative is $f^{\prime}\left(x_{k}\right)$. We will define a new method which finds the “quadratic of best fit” and uses it to compute the new iterate.
(a) Find the quadratic of best fit through the point $\left(x_{k}, f\left(x_{k}\right)\right)$, i.e., find the quadratic that goes through $\left(x_{k}, f\left(x_{k}\right)\right)$ and whose first and second derivatives at $x_{k}$ agree with $f^{\prime}\left(x_{k}\right)$ and $f^{\prime \prime}\left(x_{k}\right)$, respectively.
(b) Write down a “quadratic Newton” method for finding roots by computing the $x$ -intercept for the quadratic of best fit. To make the answer unique, use the root that is closes to $x_{k} .$ Hint: consider solving for $x_{k+1}-x_{k}$ instead of solving for $x_{k+1}$ directly.
(c) Show that the method you wrote is a consistent method, that is if the method converges, it converges to a root of $f$.
(d) How many steps are required for this method to find the solution of $f(x)=0$, where $f$ is a quadratic?

$[10=5+2+3 \mathrm{pts}]$ In this problem you will derive the most accurate quadrature rule possible that uses some values of the derivative of the function in addition to the values of the function.
(a) For an arbitrary/generic smooth function $f(x)$, find the best values for the weights $w_{-1}, w_{0}$, and $w_{1}$ in the quadrature rule:
$$
\int_{-1}^{1} f(x) d x \approx w_{-1} f^{\prime}(-1)+w_{0} f(0)+w_{1} f^{\prime}(1)
$$
(b) Verify in some way that the weights you obtained are correct.
(c) Use this rule to estimate $\int_{-1}^{1} \cos (\pi x / 2) d x$ and compare to the answer from Simpson’s rule. Which rule is more accurate for this specific problem?

$[1+5+4 \mathrm{pts}]$ An inner product $(f, g)$ for two real-valued functions $f(x)$ and $g(x)$ on an interval $[a, b]$ defines a (non-unique) set of orthogonal polynomials with respect to (w.r.t.) that inner product. Consider the interval $[-1,1]$ and the inner product given by the $n+1$ -point Gaussian quadrature rule for approximating the standard $L_{2}$ inner product $\langle f, g\rangle_{2}=\int_{a}^{b} f(x) g(x) d x$, i.e.,
$$
\langle f, g\rangle=\sum_{k=0}^{n} w_{k} f\left(x_{k}\right) g\left(x_{k}\right)
$$
where $w_{k}$ are the Gaussian quadrature weights and $x_{k}$ are the corresponding nodes. This inner product defines a new weighted $l_{2}$ norm
$$
|f|_{l_{2}}=\sum_{k=1}^{n} w_{k}\left|f\left(x_{k}\right)\right|^{2} .
$$
Take $n=2$ for this problem.
Note that to answer the questions below you do not need to know the values of $w_{k}$ and $x_{k}$ and both part $\mathrm{b}$ ) and part c) can be answered with minimal to no algebraic calculations. If you do want them, they are $x_{0}=-\sqrt{3 / 5}, x_{1}=0$, $x_{2}=\sqrt{3 / 5}, w_{0}=w_{2}=5 / 9$ and $w_{1}=8 / 9$
(a) For $q_{0}, q_{1}, q_{2} \in \mathcal{P}{2}$, give the definition of what it means to say that these polynomials are orthogonal with respect to $\langle\cdot, \cdot\rangle$ defined in (1). (b) Write down a basis for $\mathcal{P}{2}$, the space of polynomials of degree at most two, that are orthogonal w.r.t. (1), and explain how you got it and why you know they are orthogonal. You will get $1 / 2$ of the points for any answer that is an orthogonal basis. You will get full points only if you write down a basis where the degree of the polynomial increases, i.e., the first polynomial is of degree zero, the second of degree one, etc. Since orthogonal polynomials are only defined up to a constant, normalize your answers so that the coefficient in front of the highest power of $x$ is unity.
(c) Given the three function values $y_{k}=f\left(x_{k}\right), k=0,1,2$, write down an explicit formula for the optimal polynomial approximation of $f(x)$ in $\mathcal{P}{2}$ w.r.t. the norm (2), i.e., find $$ p{2}(x)=\min {p{2} \in \mathcal{P}{2}}|f-p|{l_{2}}
$$
Note: You do not need to write one complete (long) formula, you can break it into pieces and define intermediate constants as appropriate, but make sure everything is defined before it is used, and the only input is $y_{0}, y_{1}$ and
$y_{2} .$