03. Simple Numerical Algorithms I

03. Simple Numerical Algorithms I#

Last time#

  • Introduction to Python

  • String

  • Logistic operators

  • Branching and conditionals

  • Iterations and loops

Today#

Exhaustive enumeration#

  • The fundamental of algorithms

    1. Start with a guess

    2. Check if the guess is the solution

    3. If not, keep guessing until you get the solution


  • Example: finding the square root of a perfect square number \(x\)

    1. Start with a guess \(g\)

    2. If \(g \times g\) is close enough to \(x\), stop and say that \(g\) is the answer

    3. Otherwise create a new guess \(g = g + 1\)

    4. Repeat the process until close enough

# Find the square root of a perfect square number
x = 121

# Start with a guess
g = 0
while g**2 < x:
    g += 1

# Check the result
if g**2 != x:
    print(x, "is not a perfect square number.")
else:
    print("The square root of {} is {}.".format(x, g))

The square root of 121 is 11.

Exercise 3.1#

  • Finding the cube root of a perfect cube \(x\)

  • Here is your instruction:

    1. Start with a guess \(g\)

    2. If \(g^3\) is close enough to \(x\), stop and say that \(g\) is the answer

    3. Otherwise create a new guess \(g = g + 1\)

    4. Repeat the process until close enough

  • Try these two numbers:

    1. 781,229,961

    2. 853,860,064,303

Approximation#

  • Aims to find a “good enough” solution

    1. Start with a guess \(g\)

    2. Define an acceptable minimum deviation \(\epsilon\)

    3. Check if the guess is “close enough” to solution

    4. Otherwise create a new guess by \(g = g + \epsilon^2\)

    5. Repeat the process until close enough

# Find the square root of an arbitrary number
x = 121.

# Start with a guess
g = 0.0

# Define minimum deviation
epsilon = 0.01

# Step
step = epsilon**2
numGuesses = 0

while abs(g**2 - x) >= epsilon and g <= x:
    g += step
    numGuesses += 1

# Check the result
if abs(g**2 - x) >= epsilon:
    print("Failed on finding the square root of {:.2f}".format(x))
else:
    print("{:.4f} is close to the square root of {:.2f}".format(g, x))

# How many steps do we have?
print("# of guesses = {}".format(numGuesses))

10.9996 is close to the square root of 121.00
# of guesses = 109996

The blindside of exhaustive enumeration#

  • Exhaustive enumeration only works when the set of value being searched includes the answer

  • Try any number less than 1, e.g. 0.04



The concept of computational complexity#

  • How many guesses do our program need to find an approximated solution?



Find a root of an equation#

  • Previous examples have shown as how to find an approximated squared or cubic root. This is equivalent to find a root of an equation:

\[\begin{split} \begin{aligned} f(x) &= x^2 \\ f(x) &= 0 \\ x^2 &= 0 \end{aligned} \end{split}\]

  • Therefore, we can numerically “solve” an equation via the same technique. For example, we want to solve this:

\[\begin{split} f(x) = 2x^3 - 11x^2 + 2x + 15 \\ f(x) = 0 \\ 2x^3 - 11x^2 + 2x + 15 = 0 \end{split}\]

  • We just need to follow the same procedure.

    1. Start with a guess \(g\)

    2. Define an acceptable minimum deviation \(\epsilon\)

    3. Check if the guess is “close enough” to solution

    4. Otherwise create a new guess by \(g = g + \epsilon^2\)

    5. Repeat the process until close enough

# Find the root of an equation

# Create a function object
f = lambda x: 2*x**3 - 11*x**2 + 2*x + 15

# Start with a guess
g = 0.0

# Define minimum deviation
epsilon = 0.1

# Step
step = epsilon**2
numGuesses = 0

while abs(f(g) - 0) >= epsilon:
    g += step
    numGuesses += 1

# Check the result
if abs(f(g) - 0) >= epsilon:
    print("Failed on finding the root.")
else:
    print("Find an approximated root: {:.04f}".format(g))

# How many steps do we have?
print("# of guesses = {}".format(numGuesses))

Find an approximated root: 1.5000
# of guesses = 150

A small function object: lambda#

  • A lambda function is a small anonymous function.

  • A lambda function can take any number of arguments, but can only have one expression.

# Syntax
a = lambda arguments: expression

# Examples
# 1 
f = lambda x: 2*x**3 - 11*x**2 + 2*x + 15
# 2
a = lambda x, y: (x + y) * (x - y)

  • More details about the function object will be introduced in the next lecture.

# Examples
# 1 
f = lambda x: 2*x**3 - 11*x**2 + 2*x + 15

for i in range(5):
    print("f({}) = {}".format(i, f(i)))

print("="*20)

# 2
a = lambda x, y: (x + y) * (x - y)

for i in range(5):
    x = i**2
    y = i-1
    print("a({}, {}) = {}".format(x, y, a(x, y)))

f(0) = 15
f(1) = 8
f(2) = -9
f(3) = -24
f(4) = -25
====================
a(0, -1) = -1
a(1, 0) = 1
a(4, 1) = 15
a(9, 2) = 77
a(16, 3) = 247

Exercise 3.2#

  • We have already found a root of equation \(2x^3 - 11x^2 + 2x + 15 = 0\).

\[ 2x^3 - 11x^2 + 2x + 15 = 0 \]

  • However, our mathematical intuition tells us there are more roots for a cubic equation. Please find an another root of this equation.

  • Hint: try to find a root along \(x<0\).

Digression: Floating-point numbers#

  • Something you should know

  • Try this

    x = 0.
for i in range(10):
    x += 0.1
if x == 1.:
    print(x, "= 1.0")
else:
    print(x, "!= 1.0")

x = 0.
for i in range(10):
    x += 0.1
if x == 1.:
    print(x, "= 1.0")
else:
    print(x, "!= 1.0")

print(2**.5)

0.9999999999999999 != 1.0
1.4142135623730951

Floating-point numbers#

Numbers in decimal system#

  • Mantissa, exponent, and sign


  • General form


Approximation and precision#

  • Single-precision floating-point number


  • Double-precision floating-point number


  • Binary numbers: base-2 numbers

    1. \((10100110)_2 = 0 \times 2^0 + 1 \times 2^1 + 1 \times 2^2 + ... + 1 \times 2^5 + ... + 1 \times 2^7 = (166)_{10}\)

    2. \((1.1101)_2 = 1 \times 2^0 + 1 \times 2^{-1} + 1 \times 2^{-2} + 0 \times 2^{-3} + 1 \times 2^{-4} = (1.8125)_{10}\)


  • General form of floating-point number: \(\pm (1.\text{mantissa}) \times 2^{\text{exponent}}\)

Newton-Raphson method#

  • A simple and iconic technique for optimization problem (searching the local extreme values)

  • For example: finding a square root of an arbitrary number \(t\)

    1. It is equivalent to find the solution of this equation: \(f(x) = x^2 - t = 0\)

    2. The solution can be found iteratively via \(x_{n+1} = x_{n} - \frac{f(x_{n})}{f'({x_{n})}} \)

  • Gradient descent algorithm

# Example of Newton-Raphson method
# Find the square root of an arbitrary number
t = 9487
# Start with a guess
ans = t/2
# Define minimum deviation
epsilon = 0.01
numGuesses = 0

while abs(ans**2 - t) >= epsilon:
    numGuesses += 1
    ans = ans - (ans**2 - t) / (2*ans)

print("# of guesses: {}".format(numGuesses))
print("{:0.4f} is close enough to the square root of {}.".format(ans, t))

# of guesses: 9
97.4012 is close enough to the square root of 9487.

Find a root of an equation via Newton-Raphson method#

  • Again, we can numerically solve an equantion via Newton-Raphson method. For example, find a root of this equation:

\[ x^2 - 4x - 5 = 0 \]

  • You just need to follow this procedure:

    1. Start with a guess \(x_n\)

    2. Calculate the error \(E = f(x_n)\).

    3. If the error \(E\) is less than the minimum deviation \(\epsilon\), then we can say we have found an approximated root \(x_n\).

    4. If not, update the guess via \(x_{n+1} = x_{n} - \frac{f(x_{n})}{f'({x_{n})}}\) and repeat step 2 & 3.

# Find the root of an equation via Newton-Raphson method

# Create a function object
f = lambda x: x**2 - 4*x - 5

# Start with a guess
ans = 0
# Define minimum deviation
epsilon = 0.01
numGuesses = 0

while abs(f(ans) - 0) >= epsilon:
    numGuesses += 1
    ans = ans - (f(ans)) / (2*ans - 2)

print("# of guesses: {}".format(numGuesses))
print("Find an approximated root: {:.04f}".format(ans))

# of guesses: 9
Find an approximated root: -1.0009

Exercise 3.4#

  • We have already found a root of equation \(x^2 - 4x - 5 = 0\) based on the Newton-Raphson method. However, our mathematical intuition tells us there are more roots for a quadratic equation.

  • Please try to find the other root of this equation via Newton-Raphson method and explain why we can achieve this.

Contents