Wilkinson's matrix of order 4 is A= pmatrix 1&0&0&1 -1&1&0&1 -1&-1&1&1 -1&-1&-1&1 pmatrix

PHYSICS · Multi-part · Fermi University Physics · Mathematical Methods for Physics · Numerical and computational mathematics · Numerical and computational mathematics

Error, Chance and the Machine, Ch Linear systems, least squares and the singular value decomposition

Problem

Wilkinson's matrix of order 4 is A=(1001−1101−1−111−1−1−11).A=\begin{pmatrix}1&0&0&1\\-1&1&0&1\\-1&-1&1&1\\-1&-1&-1&1\end{pmatrix}. In Section 2.2 every tie between candidate pivots was broken by keeping the diagonal entry, and the growth reached 2n−1=82^{n-1} = 8. Partial pivoting allows any of the tied candidates. ((a)) Carry out Gaussian elimination with partial pivoting in exact arithmetic, breaking every tie by taking the bottom-most of the tied rows (the one with the largest row index). Give the order in which the original rows end up and the upper-triangular factor UU. ((b)) Compute the growth factor ρ4\rho_4, the largest entry (in absolute value) appearing anywhere during the elimination divided by the largest entry of AA, and compare it with the value 8 of the other tie-break. ((c)) Explain from the last column why no doubling occurs, and show that the same tie-break gives ρn=2\rho_n = 2 for Wilkinson's matrix of every order n≥2n \ge 2.

Browse the problem library