Introduction to Probability

Multivariable Calculus

Algorithms: Part II

Algorithms: Part I

Introduction to Software Design and Architecture

Calculus Two: Sequences and Series

LAFF Linear Algebra

Stanford Machine Learning

Calculus One

Computational Thinking

Effective Thinking Through Mathematics

CS50 Introduction to Computer Science


Week 10 - Linear Approximation

What is Linear Approximation

  • We call the tangent line is the linear approximation to the function at x=ax=a.
  • f(x+h)f(x)+hf(x)f(x+h) \approx f(x) + h \cdot f'(x)

Euler’s Method

  • AKA, Repeated Linear Approximation
  • Definition: Approximate values for the solution of the initial-value problem y=F(x,y)y' = F(x,y), y(x0)=y0y(x_0) = y_0, with step size h, at xn=xn1+hx_n = x_{n-1} + h, are $$y_n = y_{n-1} + hF(x_{n-1},y_{n-1}) \text{, } n=1,2,3,…$$
    • Let’s say f(0)=af(0) = a, aRa \in \mathbb{R}, and h is small number.
    • So,
      • f(h)f(0)+hF(0)f(2h)f(h)+hF(h)f(3h)f(h)+hF(2h)\begin{aligned} f(h) &\approx f(0) + h \cdot F(0) \\ f(2h) &\approx f(h) + h \cdot F(h) \\ f(3h) &\approx f(h) + h \cdot F(2h) \end{aligned}

    • Since this is just an approximation of the derivative, it’s better not to pick a point which is all the way on the left hand side of the interval, instead with the middle value:
      • f(h)f(0)+hF(h2)f(2h)f(h)+hF(3h2)f(3h)f(h)+hF(5h2)\begin{aligned} f(h) &\approx f(0) + h \cdot F(\frac{h}{2}) \\ f(2h) &\approx f(h) + h \cdot F(\frac{3h}{2}) \\ f(3h) &\approx f(h) + h \cdot F(\frac{5h}{2}) \end{aligned}

  • Take another example, why is log2319/12\log_{2}{3} \approx 19/12?
    • Since log23=log3log2\log_{2}{3} = \frac{\log3}{\log2}, Let’s separate it, to estimate log2\log2 first.
    • Set our function f(x)=logxf(x) = \log{x}, then log(1)=0\log(1) = 0, so let’s start with log(1)\log(1) with step size: 1/4 :
      • So, log(1+14)log1+14f(1+18)=0+1411+18=29\log(1+\frac{1}{4}) \approx \log{1} + \frac{1}{4} \cdot f'(1+\frac{1}{8}) = 0 + \frac{1}{4} \cdot \frac{1}{1+\frac{1}{8}} = \frac{2}{9}
        • PS, instead of using f(1)f'(1), we used f(1+18)=f(1+142)f'(1+\frac{1}{8}) = f'(1+\frac{\frac{1}{4}}{2}), which is more accurate.
        • f(x)=1xf'(x) = \frac{1}{x}
      • Then use Euler’s Method: log(1+14+14)log(1+14)+14f(1+14+18)=4099\log(1+\frac{1}{4}+\frac{1}{4}) \approx \log{(1+\frac{1}{4})} + \frac{1}{4} \cdot f'(1+\frac{1}{4}+\frac{1}{8}) = \frac{40}{99}
      • Keep doing this, we got: $$\begin{aligned}\log(2) &\approx 0.693… \ \log(3) &\approx 1.098… \ \frac{\log(3)}{\log(2)} &\approx 1.584962… \end{aligned}$$
      • And 1912=1.583ˉ\frac{19}{12} = 1.58\bar{3}, pretty close.

Newton’s Method

  • Also called the Newton-Raphson method
  • To solve the equation of the form f(x)=0f(x) = 0, so the roots of the equation(方程的根) correspond to the x-intercepts of the graph of ff. The root that we are trying to find is labeled rr in the figure.
    • We start with a first approximation x1x_1 , which is obtained by guessing,
    • Consider the tangent line L to the curve y=f(x)y = f(x) at the point (x1,f(x1))(x_1, f(x_1)) and look at the x-intercept of L, labeled x2x_2.
    • The idea behind Newton’s method is that the tangent line is close to the curve and so its x-intercept, x2x_2, is close to the x-intercept of the curve (namely, the root rr that we are seeking). Because the tangent is a line, we can easily find its x-intercept.
    • To find a formula for x2x_2 in terms of x1x_1 we use the fact that the slope of L is f(x1)f'(x_1), so its equation is:
      • yf(x1)=f(x1)(xx1)y - f(x_1) = f'(x_1)(x - x_1)
    • Since the x-intercept of L is x2x_2, we know that point (x2,0x_2, 0) is on the line, and so:
      • 0f(x1)=f(x1)(x2x1)0 - f(x_1) = f'(x_1)(x_2 - x_1)
    • If f(x1)0f'(x_1) \ne 0, we can solve this equation for x2x_2:
      • x2=x1f(x1)f(x1)x_2 = x_1 - \frac{f(x_1)}{f'(x_1)}
      • Then x3=x2f(x2)f(x2)x_3 = x_2 - \frac{f(x_2)}{f'(x_2)}
    • If we keep repeating this process, we obtain a sequence of approximations x1,x2,x3,x4,x_1, x_2, x_3, x_4, \dots as shown:
    • In general, if the nnth approximation is xnx_n and f(xn)0f'(x_n) \ne 0, then the next approximation is given by:
      • xn+1=xnf(xn)f(xn)x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}
    • If the number xnx_n become closer and closer to rr as nn becomes large, then we say that the sequence converges to rr and we write $$\lim_{n \to \infty}x_n = r$$
  • Sometimes The Newton’s method fails:
    • For example, if we choose x2x_2, then the approximation falls outside the domain of ff:
    • Then we need a better initial approximation x1x_1.

Use Newton’s Method to Divide Quickly

  • Suppose we want to calculate 1b\frac{1}{b}
  • Here is one choice: f(x)=1xbf(x) = \frac{1}{x} - b:
    • Because f(1b)=11bb=bb=0f(\frac{1}{b}) = \frac{1}{\frac{1}{b}} - b = b - b = 0
    • So we can use Newton’s Method to find 1/b.
    • f(x)=1x2xn+1=xnf(xn)f(xn)=xn1xnb1xn2xn2xn2=xn(xn+bxn2)=2xnbxn2=xn(2bxn)\begin{aligned} f'(x) &= - \frac{1}{x^2} \\ x_{n+1} &= x_n - \frac{f(x_n)}{f'(x_n)} \\ &= x_n - \frac{\frac{1}{x_n} - b}{-\frac{1}{x_n^2}} \cdot \frac{-x_n^2}{-x_n^2} \\ &= x_n - (-x_n + bx_n^2) \\ &= 2x_n - bx_n^2 \\ &= x_n \cdot (2 - bx_n) \end{aligned}