Math Problems Vault

Problem 1.5.1

Consider the following system:

\begin{aligned} 10^{-3} x - y & = 1, \\ x + y & = 0. \end{aligned}

?

(a)

Use 3-digit arithmetic with no pivoting to solve this system.

(b)

Find a system that is exactly satisfied by your solution from part (a), and note how close this system is to the original system.

(c)

Now use partial pivoting and 3-digit arithmetic to solve the original system.

(d)

Find a system that is exactly satisfied by your solution from part (c), and note how close this system is to the original system.

(e)

Use exact arithmetic to obtain the solution to the original system, and compare the exact solution with the results of parts (a) and (c).

(f)

Round the exact solution to three significant digits, and compare the result with those of parts (a) and (c).

Problem 1.5.2

(a)(b)(c)(d)

Consider the following system:

\begin{aligned} x + y & = 3, \\ -10 x + 10^{5} y & = 10^{5}. \end{aligned}

?

(a)

Use 4-digit arithmetic with partial pivoting and no scaling to compute a solution.

(b)

Use 4-digit arithmetic with complete pivoting and no scaling to compute a solution of the original system.

(c)

This time, row scale the original system first, and then apply partial pivoting with 4-digit arithmetic to compute a solution.

(d)

Now determine the exact solution, and compare it with the results of parts (a), (b), and (c).

Problem 1.5.3

With no scaling, compute the 3-digit solution of

\begin{aligned} -3 x + y & = -2, \\ 10 x - 3 y & = 7, \end{aligned}

without partial pivoting and with partial pivoting. Compare your results with the exact solution.

?

Problem 1.5.4

(a)(b)(c)(d)

Consider the following system in which the coefficient matrix is the Hilbert matrix:

\begin{aligned} x + \frac{1}{2} y + \frac{1}{3} z & = \frac{1}{3}, \\ \frac{1}{2} x + \frac{1}{3} y + \frac{1}{4} z & = \frac{1}{3}, \\ \frac{1}{3} x + \frac{1}{4} y + \frac{1}{5} z & = \frac{1}{5}. \end{aligned}

?

(a)

First convert the coefficients to 3-digit floating-point numbers, and then use 3-digit arithmetic with partial pivoting but with no scaling to compute the solution.

(b)

Again use 3-digit arithmetic, but row scale the coefficients (after converting them to floating-point numbers), and then use partial pivoting to compute the solution.

(c)

Proceed as in part (b), but this time row scale the coefficients before each elimination step.

(d)

Now use exact arithmetic on the original system to determine the exact solution, and compare the result with those of parts (a), (b), and (c).

Problem 1.5.5

(a)(b)(c)(d)

To see that changing units can affect a floating-point solution, consider a mining operation that extracts silica, iron, and gold from the earth. Capital (measured in dollars), operating time (in hours), and labor (in man-hours) are needed to operate the mine. To extract a pound of silica requires $.0055, .0011 hours of operating time, and .0093 man-hours of labor. For each pound of iron extracted, $.095, .01 operating hours, and .025 man-hours are required. For each pound of gold extracted, $960, 112 operating hours, and 560 man-hours are required.

?

(a)

Suppose that during 600 hours of operation, exactly $5000 and 3000 man-hours are used. Let $x$ , $y$ , and $z$ denote the number of pounds of silica, iron, and gold, respectively, that are recovered during this period. Set up the linear system whose solution will yield the values for $x$ , $y$ , and $z$ .

(b)

With no scaling, use 3-digit arithmetic and partial pivoting to compute a solution $(\tilde{x}, \tilde{y}, \tilde{z})$ of the system of part (a). Then approximate the exact solution $(x, y, z)$ by using your machine's (or calculator's) full precision with partial pivoting to solve the system in part (a), and compare this with your 3-digit solution by computing the relative error defined by

e_{r} = \frac{\sqrt{(x-\tilde{x})^{2}+(y-\tilde{y})^{2}+(z-\tilde{z})^{2}}}{\sqrt{x^{2}+y^{2}+z^{2}}}.

(c)

Using 3-digit arithmetic, column scale the coefficients by changing units: convert pounds of silica to tons of silica, pounds of iron to half-tons of iron, and pounds of gold to troy ounces of gold (1 lb. = 12 troy oz.).

(d)

Use 3-digit arithmetic with partial pivoting to solve the column scaled system of part (c). Then approximate the exact solution by using your machine's (or calculator's) full precision with partial pivoting to solve the system in part (c), and compare this with your 3-digit solution by computing the relative error $e_{r}$ as defined in part (b).

Problem 1.5.6

(a)(b)

Consider the system given in Example 1.5.3.

Example 1.5.3's system: $x-y=-2$ , $-9x+10y=12$ .

?

(a)

Use 3-digit arithmetic with partial pivoting but with no scaling to solve the system.

(b)

Now use partial pivoting with scaling. Does complete pivoting provide an advantage over scaled partial pivoting in this case?

Problem 1.5.7

(a)(b)(c)

Consider the following well-scaled matrix:

W_{n} = \begin{bmatrix} 1 & 0 & 0 & \cdots & 0 & 0 & 1 \\ -1 & 1 & 0 & \cdots & 0 & 0 & 1 \\ -1 & -1 & 1 & \ddots & 0 & 0 & 1 \\ \vdots & \vdots & \ddots & \ddots & \ddots & \vdots & \vdots \\ -1 & -1 & -1 & \ddots & 1 & 0 & 1 \\ -1 & -1 & -1 & \cdots & -1 & 1 & 1 \\ -1 & -1 & -1 & \cdots & -1 & -1 & 1 \end{bmatrix}.

?

(a)

Reduce $W_{n}$ to an upper-triangular form using Gaussian elimination with partial pivoting, and determine the element of maximal magnitude that emerges during the elimination procedure.

(b)

Now use complete pivoting and repeat part (a).

(c)

Formulate a statement comparing the results of partial pivoting with those of complete pivoting for $W_{n}$ , and describe the effect this would have in determining the $t$ -digit solution for a system whose augmented matrix is $[W_{n} \mid b]$ .

Problem 1.5.8

Suppose that $A$ is an $n \times n$ matrix of real numbers that has been scaled so that each entry satisfies $\left|a_{ij}\right| \leq 1$ , and consider reducing $A$ to triangular form using Gaussian elimination with partial pivoting. Demonstrate that after $k$ steps of the process, no entry can have a magnitude that exceeds $2^{k}$ .

?

Remark.

?

The previous exercise shows that there are cases where it is possible for some elements to actually attain the maximum magnitude of $2^{k}$ after $k$ steps.