MATH 417 Lecture 1

« previous | Tuesday, January 14, 2014 | next »

Numerical Analysis

Midterm 3/4 6 Quizzes Machine problems

Textbook: find cheapest one. Edition does not matter

Goals

• Programming (check!)
• Understanding

Numbers

e.g. Real ($\mathbb {R}$)

In real life, we have finite space

Floating Point Numbers

• follow the IEEE 754 binary standard (floating point arithmetic) to store numbers: 1 bit sign + 52 bits for leading digits + 11 bits exponent
• This allows for numbers between (approx) $-10^{300}$ and $10^{300}$
• Numbers in this range have about 16 digits of precision

Hence

$x=a\cdot 10^{b}$, where $1\leq a<10$ and $\left|b\right|\leq 300$

Density

• Numbers are very dense around -1, 0, and 1, but get sparser for large numbers.
• There are $10^{-16}$ apart between 0 and 1, but only $10^{-14}$ apart between 100 and 101

Numbers have to go from infinite precision to finite precision:

Approximation

Let ${\bar {x}}$ be the approximation of $x$

Two ways to approximate numbers (e.g. ${\sqrt {2}}\approx 1.41421356\ldots$)

• Rounding: ${\sqrt {2}}\approx 1.4142134$
• Truncation: ${\sqrt {2}}\approx 1.4142133$

Error

How different are $x$ and ${\bar {x}}$?

1. Absolute error: $\left|x-{\bar {x}}\right|$
2. Relative error: $\left|{\frac {x-{\bar {x}}}{x}}\right|$ (a mile and a foot is not much different than just a mile)

Example: Given $a<b$, ${\frac {a+b}{2}}$ will not always be between $a$ and $b$. A better way to implement this is a + 0.5 * (b - a), which will always be between $a$ and $b$.

First Machine Problem

$\zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}$

Approximate $\zeta (2)$:

First attempt:

s = 0
for (int i = 0; i < PARTIAL_MAX; i++) {
    s += 1.0 / (i * i)
}

This has a large error because adding small values to larger values does not always work (10²⁰ + 0.01 = 10²⁰).

Second attempt: reverse order

s = 0
for (int i = PARTIAL_MAX-1; i >= 0; i--) {
    s += 1.0 / (i * i)
}

This will give better precision

Chapter 2: Root Finding / Solving $f(x)=0$

Some things are easy ($2x+1=0$ or $x^{2}-2=0$), but how do we solve something like $\sin {\left(100x^{2}\right)}-{\frac {x}{1000}}$?

Rolle's Theorem states that for $f(a)<0$ and $f(b)>0$, where $a<b$, there exists at least one $x^{*}$ such that $f(x^{*})=0$.

Given $\epsilon$, we want to find ${\bar {x}}$ such that $\left|{\frac {{\bar {x}}-x^{*}}{b-a}}\leq \epsilon \right|$

2.1: Bisection Algorithm

A binary search algorithm.

double left = POINT_A;
double right = POINT_B;
double midpt;

for (int i = 0; i < N; i++) {
    midpt = left + 0.5 * (right - left);
    if (f(midpt) * f(right) < 0) {
        left = midpt;
    } else {
        right = midpt;
    }
}

After one step, our absolute error is $\left|x^{*}-{\bar {x}}\right|<{\frac {R-L}{2}}={\frac {b-a}{2^{2}}}$.

After $n$ steps, our absolute error is $\left|x^{*}-{\bar {x}}\right|<{\frac {R-L}{2}}={\frac {b-a}{2^{n+1}}}$

Thus our relative error is ${\frac {1}{2^{n+1}}}$.

Thus if we want $\epsilon =10^{-16}$, we choose $2^{n+1}=10^{-16}$, so $n\geq 50$