Nonlinear equations Flashcards Preview

Numerical - Michaelmas > Nonlinear equations > Flashcards

Flashcards in Nonlinear equations Deck (59):
1

What is the big question about non-linear equations?

How do we find the roots of the equations

2

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

Iterative method

3

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

Plot the graph so you can check your answer

4

What is the notation for any root?

x*

5

What is the Intermediate Value Theorem?

A image thumb
6

What is the Interval bisection algorithm?

A image thumb
7

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

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.

8

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

A image thumb
9

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

A image thumb
10

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

A image thumb
11

What is the general method for fixed point iteration?

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 xand iterate xk+1 = g(xk) until |xk+1 - xk| is sufficiently small.

12

What is a problem with fixed point iteration?

Not all rearrangements g(x) = x will converge

13

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

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

A image thumb
14

What is the Contraction Mapping Theorem?

A image thumb
15

Prove the following theorem.

Q image thumb

A image thumb
16

How do you show g is a contraction map?

A image thumb
17

What is the Local Convergence theorem?

A image thumb
18

Prove the following theorem.

Q image thumb

A image thumb
19

What do we compare to measure the speed of convergence?

The error |x* - xk+1| to the error at the previous step |x* - xk|

20

Define linear convergence.

A image thumb
21

What is λ called?

The rate or ratio

22

What λ shows superlinear convergence?

0

23

What is meant by superlinear convergence?

The error decreases ar a faster and faster rate

24

What is the theorem about liner and superlinear convergence?

A image thumb
25

Prove the following theorem.

Q image thumb

A image thumb
26

How can we further classify superlinear convergence?

By the order of convergence, defined as 

A image thumb
27

What is a famous iterative method that usually converges superlinearly?

Newton's Method

28

What is the iterative function for Newton's method?

A image thumb
29

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

A image thumb
30

Prove that Newton's method gives superlinear convergence.

A image thumb
31

What does the forth column in the following show?

Q image thumb

The convergence is quadratic 

32

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

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

33

Write the following in matrix form.

Q image thumb

A image thumb
34

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

A image thumb
35

Write the following in a more simplified version.

Q image thumb

A image thumb
36

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

Q image thumb

Rearrange for xk+1 

A image thumb
37

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

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

38

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

Quadratic provided that J(x*) is non singular

39

What is the Aitken a trick for?

Accelerating the convergence of a linearly convergent sequence 

40

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

A image thumb
41

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

A image thumb
42

What is the aim of Aitken acceleration?

The extrapolation will get closer to x٭ than before

43

What is one problem with Aitken acceleration?

Rounding erros can affect ∆2xk

44

What does ∆xk equal?

xk-1 - xk

45

What does ∆2xk equal?

∆(∆xk)

46

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

A image thumb
47

What are three drawbacks of Newton's method?

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

48

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

Quasi-Newton method

49

What is the formula for a quasi-Newton method?

A image thumb
50

What does gstand for in the following?

Some easily-computed approximation to f'(xk)

51

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

A image thumb
52

How many function evaluations does the following require per iteration?

Q image thumb

Two

53

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

Q image thumb

A image thumb
54

What is the following method called?

Q image thumb

The secant method 

55

Why is the secant method a two-point method?

A image thumb
56

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

A image thumb
57

What is the formula for the secant method?

A image thumb
58

Prove the following theorem.

Q image thumb

A image thumb
59