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?

6

What is the Interval bisection algorithm?

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?

9

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

10

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

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.

14

What is the Contraction Mapping Theorem?

15

Prove the following theorem.

16

How do you show g is a contraction map?

17

What is the Local Convergence theorem?

18

Prove the following theorem.

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.

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?

25

Prove the following theorem.

26

How can we further classify superlinear convergence?

By the order of convergence, defined as 

27

What is a famous iterative method that usually converges superlinearly?

Newton's Method

28

What is the iterative function for Newton's method?

29

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

30

Prove that Newton's method gives superlinear convergence.

31

What does the forth column in the following show?

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.

34

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

35

Write the following in a more simplified version.

36

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

Rearrange for xk+1 

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 λ.

41

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

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)?

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?

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?

52

How many function evaluations does the following require per iteration?

Two

53

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

54

What is the following method called?

The secant method 

55

Why is the secant method a two-point method?

56

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

57

What is the formula for the secant method?

58

Prove the following theorem.

59