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{ℝ}$)

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\le a<10$ and $\left|b\right|\le 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 $\overline{x}$ be the approximation of $x$

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

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

Error

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

1. Absolute error: $|x-\overline{x}|$
2. Relative error: $\left|\frac{x-\overline{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}^{\mathrm{\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 $ϵ$, we want to find $\overline{x}$ such that $|\frac{\overline{x}-x^{*}}{b-a}\le ϵ|$

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 $|x^{*}-\overline{x}|<\frac{R-L}{2}=\frac{b-a}{2^2}$.

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

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

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