MA/CS/EGR 537 Assignment 6 Answers/Grading

MA/CS/EGR 537: Assignment 6 Answers/Grading

(a) In order to simplify this part, let's introduce a change in the notation. Let

Method	Original notation	Changes to
Newton	e_i⁽²⁾ = k₂ (e_i-1⁽²⁾)²	e_i = k (e_i-1)²
Newton-Chord	e_i = k (e_{i k₃ (e_i-1⁽³⁾)}	E_i = K e_i-1

A table of error contractions looks like the following:

Iteration	Newton	Newton-Chord
2	k(e₁)²	Ke₁
3	k³(e₁)⁴	K²e₁
4	k⁷(e₁)⁸	K³e₁
5	k¹⁵(e₁)¹⁶	K⁴e₁
6	k³¹(e₁)³²	K⁵e₁
7	k⁶³(e₁)⁶⁴	K⁶e₁
8	k¹²⁷(e₁)¹²⁸	K⁷e₁
9	k²⁵⁵(e₁)²⁵⁶	K⁸e₁

Under the assumptions of the problem, at some pair of iterations, k^{2^p-1}(e₁)^{2^p} ~ K^qe₁, where C₂=2^p and C₃=q. So, K^q ~ (ke₁)^{2^p-1}. Assuming that K=O(ke₁), then q=C₃~2^C₂-1. We get the desired result by an appropriate definition of the starting guess, namely the one after the first iteration.

(b) The first iteration is the same for both methods, namely

Computes J(x₀) and F(x₀)
Factor the matrix J(x₀) and then solve J(x₀)c₀ = F(x₀) and updates.

Cost: L = CN³ + (A+D)N² + BN.

The rest of the iterations, the Newton method does the following:

Computes J(x_i) and F(x_i)
Factor the matrix J(x_i) and then solve J(x_i)c_i = F(x_i) and updates.

Cost: L = CN³ + (A+D)N² + BN.

The Newton-Chord method does the following:

Computes F(y_i)
Solve J(x₀)c₀ = F(y_i) and updates.

Cost: M = AN² + BN.

Total Costs:

Method>	Cost
Newton	C₂L
Newton-Chord	(C₃-1)M+L

(c) Ignore the first iteration. Without loss of generality, assume that C₂ and C₃ have been adjusted down by 1 each. Then, without loss of generality, we must only compare

C₂ C N³ with C₃ D N² = 2^C₂ D N². Hence, the Newton-Chord method (3) is cheaper whenever 2^C₂ < (C/D)N. This bound is independent of the sizes of N and C₂. As a guide, however,

N	C₂
	Small	Large
Small	(*)	Newton
Large	Newton-Chord	(*)

Note that (*) in the table means that the formula for the switch over should be used instead of intuition.

Cheers,
Craig C. Douglas