Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Numerical - Michaelmas > Nonlinear equations > Flashcards

Nonlinear equations Flashcards

1
Q

What is the big question about non-linear equations?

A

How do we find the roots of the equations

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A

Iterative method

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

Plot the graph so you can check your answer

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is the notation for any root?

A

x*

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is the Intermediate Value Theorem?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the Interval bisection algorithm?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is the general method for fixed point iteration?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is a problem with fixed point iteration?

A

Not all rearrangements g(x) = x will converge

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is the Contraction Mapping Theorem?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Prove the following theorem.

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

How do you show g is a contraction map?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is the Local Convergence theorem?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Prove the following theorem.

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What do we compare to measure the speed of convergence?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Define linear convergence.

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What is λ called?

A

The rate or ratio

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What λ shows superlinear convergence?

A

0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What is meant by superlinear convergence?

A

The error decreases ar a faster and faster rate

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is the theorem about liner and superlinear convergence?

A
25
Q

Prove the following theorem.

A
26
Q

How can we further classify superlinear convergence?

A

By the order of convergence, defined as

27
Q

What is a famous iterative method that usually converges superlinearly?

A

Newton’s Method

28
Q

What is the iterative function for Newton’s method?

A
29
Q

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

A
30
Q

Prove that Newton’s method gives superlinear convergence.

A
31
Q

What does the forth column in the following show?

A

The convergence is quadratic

32
Q

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

A

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

33
Q

Write the following in matrix form.

A
34
Q

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

A
35
Q

Write the following in a more simplified version.

A
36
Q

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

A

Rearrange for xk+1

37
Q

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

A

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

38
Q

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

A

Quadratic provided that J(x*) is non singular

39
Q

What is the Aitken a trick for?

A

Accelerating the convergence of a linearly convergent sequence

40
Q

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

A
41
Q

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

A
42
Q

What is the aim of Aitken acceleration?

A

The extrapolation will get closer to x٭ than before

43
Q

What is one problem with Aitken acceleration?

A

Rounding erros can affect ∆2xk

44
Q

What does ∆xk equal?

A

xk-1 - xk

45
Q

What does ∆2xk equal?

A

∆(∆xk)

46
Q

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

A
47
Q

What are three drawbacks of Newton’s method?

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

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

A

Quasi-Newton method

49
Q

What is the formula for a quasi-Newton method?

A
50
Q

What does gk stand for in the following?

A

Some easily-computed approximation to f’(xk)

51
Q

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

A
52
Q

How many function evaluations does the following require per iteration?

A

Two

53
Q

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

A
54
Q

What is the following method called?

A

The secant method

55
Q

Why is the secant method a two-point method?

A
56
Q

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

A
57
Q

What is the formula for the secant method?

A
58
Q

Prove the following theorem.

A
59
Q
A

Numerical - Michaelmas (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions