MATH 417 Lecture 14

« previous | Thursday, February 27, 2014 | next »

End Exam 1 content

Exam Review

Section 2.1: Bisection

(#10) Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) = (x+2)\,(x+1)^2 \, x \, (x-1)^3 \, (x-2)}

Find root in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [-1.5, 2.5] = \left[ -\frac{3}{2}, \frac{5}{2} \right]} using bisection:

f(-1.5) < 0
f(2.5) > 0
f(0.5) > 0
f(-0.5) < 0
f(0) = 0 ← stop

Section 2.2: Fixed Point

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) = x^3 - x - 1 = 0} for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in [1,2]}

Find $x=g(x)$ and take Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_0 \in [a,b]} and recursively find Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_{n+1} = g(p_n)} for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = 0, 1, 2, \ldots}

for any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in [a,b]} , we need Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x) \in [a,b]}
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\max_{x\in [a,b]} \left| g'(x) \right| = k) < 1}

$\left|p_{n}-p\right|\leq k^{n}\,\max {(b-p_{0},p_{0}-a)}$

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left| p_n - p \right| \le \frac{k^n}{1-k} \, \left| p_1 - p_0 \right|}

In our case, we take Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x = \sqrt[3]{x+1}} :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 < g(1) \le g(2) = 3^{\frac{1}{3}} < 2}
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left| g'(x) \right| = \frac{1}{3} \, \frac{1}{(x+1)^{\frac{2}{3}}} \le \frac{1}{3 \cdot 2^{\frac{2}{3}}} = k}

Find the number of iterations needed to get accuracy $10^{-3}$ :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left| p_n - p \right| \le \left( \frac{1}{3 \cdot 4^{\frac{1}{3}}} \right)^n \, \max(p_0 - 1, 2 - p_0)}

Choose Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_0 = \frac{3}{2}} , now

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \left( 3 \cdot 4^{\frac{1}{3}} \right)^{-n} \cdot \frac{1}{2} &\le 10^{-3} \\ \left( 3 \cdot 4^{\frac{1}{3}} \right)^{-n} &\le 2 \cdot 10^{-3} \\ -n \, \ln{\left( 3 \cdot 4^{\frac{1}{3}} \right)} &\le \ln{2} - 3 \ln{10} \\ n &\ge \frac{3\ln{10}-\ln{2}}{\ln{3} + \frac{1}{3} \, \ln{4}} = \frac{9\ln{10}-3\ln{2}}{3\ln{3}+\ln{4}} \approx 3.981909816 \\ \end{align}}

Therefore take Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = 4}

Newton's Method

$x=g(x)$ , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g(x) = x - \frac{f(x)}{f'(x)}}

If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} is concave-up, choose right endpoint: Newton's method works best when Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f'' > 0} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f' > 0}

In our example above, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_{n+1} = p_n - \frac{p_n^3 - p_n - 1}{3p_n^2 - 1}}

Chapter 3: Interpolation

Given Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_0, x_1, \ldots x_n} , interpolate Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)} as a polynomial $p_{n}(x)$

Lagrange

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) = \sum_{i=1}^n f(x_i) \, \prod_{j=0; j \ne i}^n \frac{(x-x_j)}{(x_i - x_j)} + \underbrace{ \frac{f^{(n+1)}(\xi)}{(n+1)!} \, (x-x_0) \, (x-x_1) \dots (x-x_n) }_{\mbox{error}}}

Newton

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) = f(x_0) + f[x_0, x_1] (x-x_0) + \dots + f[x_0, x_1, \ldots, x_n] (x-x_0) \dots (x-x_n) + \underbrace{ \frac{f^{(n+1)}(\xi)}{(n+1)!} \, (x-x_0) \, (x-x_1) \dots (x-x_n) }_{\mbox{error}}}

Example: (9th ed: 124 #7): Find polynomial that interpolates at 0, 1, 2, 3 at the point Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x = \frac{5}{2}} (that is, find $p_{0,1,2,3}\left({\frac {5}{2}}\right)$ ) given:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_{0,1}(x) = 2x+1} (the line through $f(0)$ and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(1)} )
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_{0,2}(x) = x+1} (the line through Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(0)} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(2)} )
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_{1,2,3}\left( \frac{5}{2} \right) = 3} (the parabola through Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(1)} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(2)} , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(3)} has value Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3} at $x={\frac {5}{2}}$

We know the lines through f(0)

x   f(x)
--------
0    1
        2
1    3       -1
        0             (a-1)/6
2    3       (a-3)/2
        a-3
3    a

Now Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_{1,2,3}(x) = 3 + 0(x-1) + \frac{a-3}{2} \, (x-1) \, (x-2)} , hence Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_{1,2,3} \left( \frac{5}{2} \right) = 3 = 3 + \frac{a-3}{2} \, \left( \frac{3}{2} \right) \, \left( \frac{1}{2} \right)} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a = 3} .

Therefore, our interpolating polynomial Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_{0,1,2,3}} is

p_{0,1,2,3}(x)=3+{\frac {1}{3}}\,\left(x-3\right)\,\left(x-2\right)\,\left(x-1\right)

and evaluated at Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x = \frac{5}{2}} , we get Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_{0,1,2,3} \left( \frac{5}{2} \right) = \frac{23}{8}}

Hermite

A tomato is launched at a height of 10 ft with an initial speed of 10 ft/s. The tomato hits a person standing 50 ft away and has a final speed of -20 ft/s

 x   f(x)  f'(x)

 0    10
            10
 0    10          -51/250
            -1/5           -12/3125
 50   0           -99/250
            -20
 50   0

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H_3(x) = 10 + 10x - \frac{51}{250} \, x^2 - \frac{12}{3125} \, x^2 \, (x-50)}

Whoa! The trajectory of an object is parabolic (disregarding friction or air resistance), and given only two points with derivatives (positions and velocities), we can reconstruct the entire trajectory exactly. The same can be done with three points, since three points uniquely defines a parabola.

Section 4.1: Differentiation

(9th ed. #22) Approximate Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f'(x_0)} using Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x_0-h)} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x_0)} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x_0 + h)} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x_0 + 2h)} to accuracy Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(h^3)}

Taylor series around Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x_0)} :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} f(x_0-h) &= f(x_0) - h \, f'(x_0) + \frac{h^2}{2} \, f''(x_0) - \frac{h^3}{6} \, f'''(x_0) + O(h^4) \\ f(x_0+h) &= f(x_0) + h \, f'(x_0) + \frac{h^2}{2} \, f''(x_0) + \frac{h^3}{6} \, f'''(x_0) + O(h^4) \\ f(x_0+2h) &= f(x_0) + 2h \, f'(x_0) + \frac{(2h)^2}{2} \, f''(x_0) + \frac{(2h)^3}{6} \, f'''(x_0) + O(h^4) \end{align}}

Multiply equations by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} , respectively and solve for:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \, f(x_0 - h) + B \, f(x_0 + h) + C \, f(x_0 + 2h) = (A + B + C) \, f(x_0) + h(-A + B + 2C) \, f'(x_0)} .

We get the following system of equations

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{cases} -A + B + 2C &= 1 \\ A + B + 4C &= 0 \\ -A + B + 8C &= 0 \end{cases} \quad \implies \quad \left\langle A,B,C \right\rangle = \left\langle -\frac{1}{3}, 1, -\frac{1}{6} \right\rangle}

Alternatively, we can find Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_3'(x_0)} via the interpolating polynomial above, but that usually involves more work.

Sections 4.3 and 4.7: Integration

(9th ed. #20)

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \int_{0}^{1} f(x) \,\mathrm{d}x \approx \frac{1}{2} \, f(x_0) + c_1 \, f(x_1)}

Find the rule with best DAC (which will be the Gaussian rule since scaling factor is 1/2)

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \int_{0}^{1} 1 \,\mathrm{d}x = 1 = \frac{1}{2} + c_1} , so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_1 = \frac{1}{2}}
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \int_{0}^{1} x \,\mathrm{d}x = \frac{1}{2} = \frac{1}{2} \, x_0 + \frac{1}{2} \, x_1 }
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \int_{0}^{1} x^2 \,\mathrm{d}x = \frac{1}{3} = \frac{1}{2} \, x_0^2 + \frac{1}{2} \, x_1^2}

Solve for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_0, x_1 = \frac{1}{2} \pm \frac{\sqrt{3}}{6}} .

Degree of accuracy is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2 \cdot 2 - 1 = 3} .

Note: Every Gaussian rule is symmetric

(9th ed. #13)

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \int_{0}^{2} f(x) \, \mathrm{d}x \approx 4} by trapezoid and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \approx 2} by simpson's rule. Find Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(1)} .

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{cases} \frac{2}{2} \, \left( f(0) + f(2) \right) &= 4 \\ \frac{2}{6} \, \left( f(0) + 4f(1) + f(2) \right) &= 2 \end{cases} \quad \implies \quad 4 + 4f(1) = 6 \quad \implies \quad f(1) = \frac{1}{2}}