Math Problems Vault

Problem 1.6.1

Consider the ill-conditioned system of Example 1.6.1:

\begin{aligned} .835 x + .667 y & = .168, \\ .333 x + .266 y & = .067. \end{aligned}

?

(a)

Describe the outcome when you attempt to solve the system using 5-digit arithmetic with no scaling.

(b)

Again using 5-digit arithmetic, first row scale the system before attempting to solve it. Describe to what extent this helps.

(c)

Now use 6-digit arithmetic with no scaling. Compare the results with the exact solution.

(d)

Using 6-digit arithmetic, compute the residuals for your solution of part (c), and interpret the results.

(e)

For the same solution obtained in part (c), again compute the residuals, but use 7-digit arithmetic this time, and interpret the results.

(f)

Formulate a concluding statement that summarizes the points made in parts (a)--(e).

Problem 1.6.2

(a)(b)

Perturb the ill-conditioned system given in Exercise 1.6.1 above so as to form the following system:

\begin{aligned} .835 x + .667 y & = .1669995, \\ .333 x + .266 y & = .066601. \end{aligned}

?

(a)

Determine the exact solution, and compare it with the exact solution of the system in Exercise 1.6.1.

(b)

On the basis of the results of part (a), formulate a statement concerning the necessity for the solution of an ill-conditioned system to undergo a radical change for every perturbation of the original system.

Problem 1.6.3

(a)(b)(c)

Consider the two straight lines determined by the graphs of the following two equations:

\begin{aligned} .835 x + .667 y & = .168, \\ .333 x + .266 y & = .067. \end{aligned}

?

(a)

Use 5-digit arithmetic to compute the slopes of each of the lines, and then use 6-digit arithmetic to do the same. In each case, sketch the graphs on a coordinate system.

(b)

Show by diagram why a small perturbation in either of these lines can result in a large change in the solution.

(c)

Describe in geometrical terms the situation that must exist in order for a system to be optimally well-conditioned.

Problem 1.6.4

(a)(b)(c)

Using geometric considerations, rank the following three systems according to their condition.

?

(a)

\begin{aligned} 1.001 x - y & = .235, \\ x + .0001 y & = .765. \end{aligned}

(b)

\begin{aligned} 1.001 x - y & = .235, \\ x + .9999 y & = .765. \end{aligned}

(c)

\begin{aligned} 1.001 x + y & = .235, \\ x + .9999 y & = .765. \end{aligned}

Problem 1.6.5

Determine the exact solution of the following system:

\begin{aligned} 8 x + 5 y + 2 z & = 15, \\ 21 x + 19 y + 16 z & = 56, \\ 39 x + 48 y + 53 z & = 140. \end{aligned}

Now change $15$ to $14$ in the first equation and again solve the system with exact arithmetic. Is the system ill-conditioned?

?

Problem 1.6.6

Show that the system

\begin{aligned} v - w - x - y - z & = 0, \\ w - x - y - z & = 0, \\ x - y - z & = 0, \\ y - z & = 0, \\ z & = 1, \end{aligned}

is ill-conditioned by considering the following perturbed system:

\begin{aligned} v - w - x - y - z & = 0, \\ -\frac{1}{15} v + w - x - y - z & = 0, \\ -\frac{1}{15} v + x - y - z & = 0, \\ -\frac{1}{15} v + y - z & = 0, \\ -\frac{1}{15} v + z & = 1. \end{aligned}

?

Problem 1.6.7

(a)(b)

Let $f(x) = \sin \pi x$ on $[0, 1]$ . The object of this problem is to determine the coefficients $\alpha_{i}$ of the cubic polynomial

p(x) = \sum _{i=0}^{3} \alpha _{i} x^{i}

that is as close to $f(x)$ as possible in the sense that

\begin{aligned} r & = \int _{0}^{1} [f(x) - p(x)]^{2} \, dx \\ & = \int _{0}^{1} [f(x)]^{2} \, dx - 2 \sum _{i=0}^{3} \alpha _{i} \int _{0}^{1} x^{i} f(x) \, dx + \int _{0}^{1} \left( \sum _{i=0}^{3} \alpha _{i} x^{i} \right)^{2} dx \end{aligned}

is as small as possible.

?

(a)

In order to minimize $r$ , impose the condition that $\partial r / \partial \alpha_{i} = 0$ for each $i = 0, 1, 2, 3$ , and show this results in a system of linear equations whose augmented matrix is $[H_{4} \mid b]$ , where $H_{4}$ and $b$ are given by

H_{4} = \begin{bmatrix} 1 & \dfrac {1}{2} & \dfrac {1}{3} & \dfrac {1}{4} \\ ]2mm] \dfrac {1}{2} & \dfrac {1}{3} & \dfrac {1}{4} & \dfrac {1}{5} \\[2mm] \dfrac {1}{3} & \dfrac {1}{4} & \dfrac {1}{5} & \dfrac {1}{6} \\ ]2mm] \dfrac {1}{4} & \dfrac {1}{5} & \dfrac {1}{6} & \dfrac {1}{7} \end{bmatrix} \quad \text{and} \quad b = \begin{bmatrix} \dfrac {2}{\pi } \\[2mm] \dfrac {1}{\pi } \\ ]2mm] \dfrac {1}{\pi } - \dfrac {4}{\pi ^{3}} \\[2mm] \dfrac {1}{\pi } - \dfrac {6}{\pi ^{3}} \end{bmatrix}.

Any matrix $H_{n}$ that has the same form as $H_{4}$ is called a Hilbert matrix of order $n$ .

(b)

Systems involving Hilbert matrices are badly ill-conditioned, and the ill-conditioning becomes worse as the size increases. Use exact arithmetic with Gaussian elimination to reduce $H_{4}$ to triangular form. Assuming that the case in which $n = 4$ is typical, explain why a general system $[H_{n} \mid b]$ will be ill-conditioned. Notice that even complete pivoting is of no help.