Nonlinear equations

Question 1

What is the big question about non-linear equations?

Answer 1

How do we find the roots of the equations

Question 2

When there is no explicit formula to find the root(s) what types of methods do we have to use?

Answer 2

Iterative method

Question 3

What is the first step when trying to find any root?

Answer 3

Plot the graph so you can check your answer

Question 4

What is the notation for any root?

Answer 4

x_*

Question 5

What is the Intermediate Value Theorem?

Answer 5

Question 6

What is the Interval bisection algorithm?

Answer 6

Question 7

If f(a)f(b) < 0 what does this tell you about f?

Answer 7

It changes sign at leats once in [a,b] , so by the IVT theorem there must be a point x_* ∈ [a,b] where f(x_*) = 0.

Question 8

What length does the interval have after k iterations of interval bisection?

Answer 8

Question 9

What is the error of the midpoint of an interval after k interations of interval bisection?

Answer 9

Question 10

How many iterations do we need to make the error of the midpoint |m_k - x_*| ≤ δ?

Answer 10

Question 11

What is the general method for fixed point iteration?

Answer 11

Transform f(x) = 0 into the form g(x) = x, so that a root x_* of f is a fixed point of g, meaning g(x_*) = x_*. To find x_*, we start from some initial guess x₀ and iterate x_k+1 = g(x_k) until |x_k+1 - x_k| is sufficiently small.

Question 12

What is a problem with fixed point iteration?

Answer 12

Not all rearrangements g(x) = x will converge

Question 13

A contractiln map f, is a map L ➝ L (for some closed interval) satisfying?

Answer 13

For some λ< 1 and for all x, y ∈ L.

Question 14

What is the Contraction Mapping Theorem?

Answer 14

Question 15

Prove the following theorem.

Answer 15

Question 16

How do you show g is a contraction map?

Answer 16

Question 17

What is the Local Convergence theorem?

Answer 17

Question 18

Prove the following theorem.

Answer 18

Question 19

What do we compare to measure the speed of convergence?

Answer 19

The error |x_* - x_k+1| to the error at the previous step |x_* - x_k|

Question 20

Define linear convergence.

Answer 20

Question 21

What is λ called?

Answer 21

The rate or ratio

Question 22

What λ shows superlinear convergence?

Answer 22

0

Question 23

What is meant by superlinear convergence?

Answer 23

The error decreases ar a faster and faster rate

Question 24

What is the theorem about liner and superlinear convergence?

Answer 24

Question 25

Prove the following theorem.

Answer 25

Question 26

How can we further classify superlinear convergence?

Answer 26

By the order of convergence, defined as

Question 27

What is a famous iterative method that usually converges superlinearly?

Answer 27

Newton's Method

Question 28

What is the iterative function for Newton's method?

Answer 28

Question 29

How can derive the iteration function for Newton's method algebraically?

Answer 29

Question 30

Prove that Newton's method gives superlinear convergence.

Answer 30

Question 31

What does the forth column in the following show?

Answer 31

The convergence is quadratic

Question 32

Why don't you want to start iterative near f'(x) = 0 in Newton's method?

Answer 32

You will get stuck in a infinite loop and not find the root.

Question 33

Write the following in matrix form.

Answer 33

Question 34

What is the Jacobian matrix J(x_k) equal to?

Answer 34

Question 35

Write the following in a more simplified version.

Answer 35

Question 36

How do you derive Newton's method for systems from the following?

Answer 36

Rearrange for **x**_k+1

Question 37

If m=1, in Newton's method for systems what does the Jacobian reduce too?

Answer 37

1\f'(x), which is the usual scalar formula

Question 38

What is the convergence for Newton's method for systems?

Answer 38

Quadratic provided that J(x_*) is non singular

Question 39

What is the Aitken a trick for?

Answer 39

Accelerating the convergence of a linearly convergent sequence

Question 40

If we have the following and take two successibe iterations show how we can eliminate λ.

Answer 40

Question 41

In Aitken acceleration what do we replace every third iterate by?

Answer 41

Question 42

What is the aim of Aitken acceleration?

Answer 42

The extrapolation will get closer to x_٭ than before

Question 43

What is one problem with Aitken acceleration?

Answer 43

Rounding erros can affect ∆²x_k

Question 44

What does ∆x_k equal?

Answer 44

x_k-1 - x_k

Question 45

What does ∆²x_k equal?

Answer 45

∆(∆x_k)

Question 46

What is the formula for solving f(x) = 0 with the iteration function g(x) = x + f(x)?

Answer 46

Question 47

What are three drawbacks of Newton's method?

Answer 47

1. The derivative must be computed at each iteration 2. Expensive to compute 3. Formula to do so might not be available

Question 48

What method can we use instead of a Newton method when we don't want to find a derivative?

Answer 48

Quasi-Newton method

Question 49

What is the formula for a quasi-Newton method?

Answer 49

Question 50

What does g_k stand for in the following?

Answer 50

Some easily-computed approximation to f'(x_k)

Question 51

What is the formula for Steffensen's method and what g_k do we use?

Answer 51

Question 52

How many function evaluations does the following require per iteration?

Answer 52

Two

Question 53

Once the iteration has started for the following quasi-Newton method we can appoximate f'(x_k) by what backward difference?

Answer 53

Question 54

What is the following method called?

Answer 54

The secant method

Question 55

Why is the secant method a two-point method?

Answer 55

Question 56

What is the theorem about the order of convergence of the secant method?

Answer 56

Question 57

What is the formula for the secant method?

Answer 57

Question 58

Prove the following theorem.

Answer 58