Warning

This page is located in archive.
Go to the latest version of this course pages.
Go the latest version of this page.

Suppose we have a real function of one variable $f: \mathbb{R} \rightarrow \mathbb{R}$ continuous on the interval $[a, b] \in \mathbb{R}$, for which the function values in the extreme points of this interval have the opposite sign. The bisection method is an iterative algorithm for finding the root of such a function on a specified interval. In each iteration, the bisection method performs the following two steps:

**Finding the center point:**the method finds the center of the given interval $$ c = \frac{a + b}{2}. $$**Update of the search interval:**if the function values $f(a)$ and $f(c)$ have the same sign, then the new interval for the root search is $[c, b]$. Otherwise, the new interval is $[a, c]$.

The above two steps are repeated until the desired accuracy is reached or the maximum number of iterations is reached. As a stopping criterion, we can use the functional value at point $c$, i.e. the algorithm will terminate if $|f(c)| < \varepsilon$ for the specified tolerance $\varepsilon \in \mathbb{R}$.

The regula falsi method differs from the bisection method only in how it selects the $c$ point. The following formula is used for this method

$$ c = \frac{a\cdot f(b) - b\cdot f(a)}{f(b) - f(a)}. $$

Implement a `findroot`

function that finds the root of a given function on a given interval. The `findroot`

function must have the following input arguments (in the order listed):

`method`

: the method that will be used to find the root,`f`

: function of one variable whose root we want to find,`a`

: lower limit of the interval,`b`

: upper limit of the interval.

Choose the appropriate types for all input parameters of the `findroot`

function. Use the following type hierarchy to differentiate the root search method.

abstract type BracketingMethod end struct Bisection <: BracketingMethod end struct RegulaFalsi <: BracketingMethod end

Additionally, the `findroot`

function must accept the following keyword arguments (values after `=`

are values):

`atol = 1e-8`

: algorithm tolerance,`maxiter = 1000`

: maximum number of iterations.

When implementing, note that the bisection method and the regula falsi method differ only in the selection of a new point. Write a general `findroot`

function for both methods. Use multiple-dispatch and write a `midpoint`

function that will return a new point based on the method used. This function must have the following input arguments (in the order listed):

`method`

: the method that will be used to find the root,`f`

: function of one variable whose root we want to find,`a`

: lower limit of the interval,`b`

: upper limit of the interval.

The `findroot`

function must also meet the following properties:

- The function must check that
`a < b`

holds, and if not, it must swap variables to satisfy this inequality. - If the function is given a root to look for, the function must return this root without any further calculation.
- If the function values at the endpoints of the specified interval have the same sign, the function must return DomainError with with a meaningful error message.

courses/b0b36jul/en/hw/hw1.txt · Last modified: 2023/01/16 18:00 by adamluk3