diff options
| author | Elizabeth Hunt <elizabeth.hunt@simponic.xyz> | 2023-10-18 12:49:39 -0600 |
|---|---|---|
| committer | Elizabeth Hunt <elizabeth.hunt@simponic.xyz> | 2023-10-18 12:49:39 -0600 |
| commit | 9e7166a52e94d8e15bf2dbfe00026f21f76630a9 (patch) | |
| tree | bb4d7114d5f91fa128375347ab4249a4c35408f2 /notes/Oct-18.org | |
| parent | 1b4d91e623a083690ac6554d1aeaa38b75469908 (diff) | |
| download | cmath-9e7166a52e94d8e15bf2dbfe00026f21f76630a9.tar.gz cmath-9e7166a52e94d8e15bf2dbfe00026f21f76630a9.zip | |
oct 16, 18 notes. add unit tests with utest, and bisection root finding methods
Diffstat (limited to 'notes/Oct-18.org')
| -rw-r--r-- | notes/Oct-18.org | 18 |
1 files changed, 18 insertions, 0 deletions
diff --git a/notes/Oct-18.org b/notes/Oct-18.org new file mode 100644 index 0000000..0104164 --- /dev/null +++ b/notes/Oct-18.org @@ -0,0 +1,18 @@ +Error Analysis Of Bisection Root Finding: + +e_0 \le b - a = b_0 - a_0 +e_1 \le b_1 - a_1 = 1/2(b_0 - a_0) +e_2 \le b_2 - a_2 = 1/2(b_1 - a_1) = (1/2)^2(b_0 - a_0) +e_k \le b_k - a_k = 1/2(b_{k-1} - a_{k-1}) = \cdots = (1/2)^k (b_0 - a_0) + + +e_k \le (1/2)^k (b_0 - a_0) = tolerance +\Rightarrow log(1/2^k) + log(b_0 - a_0) = log(tolerance) +\Rightarrow k log(1/2) + log(tolerance) - log(b_0 - a_0) +\Rightarrow k log(1/2) = log(tolerance / (b_0 - a_0)) +\Rightarrow k \ge log(tolerance / (b_0 - a_0)) / log(1/2) + +The Bisection Method applied to an interval [a, b] for a continous function will reduce the error +each time through by at least one half. + +| x_{k+1} - x_k | \le 1/2|x_k - x^* | |