Lära Iterative Methods for Root Finding

Root-finding is a central topic in numerical mathematics, where the goal is to find solutions to equations of the form $f(x) = 0$ . Analytical solutions are not always possible, especially for nonlinear equations, so you often turn to iterative methods. These methods generate a sequence of approximations that converge to the actual root.

Common iterative techniques include the bisection method and the Newton-Raphson method:

The bisection method is a robust and simple approach that requires only the function and an interval where the function changes sign;
The Newton-Raphson method uses tangents and requires the derivative of the function, often converging more quickly but being more sensitive to initial guesses and function behavior.


              123456789101112131415161718192021222324
            
# Bisection method for finding a root of f(x) = 0
bisection_method <- function(f, a, b, tol = 1e-7, max_iter = 100) {
  if (f(a) * f(b) >= 0) {
    stop("Function must change sign on [a, b]")
  }
  for (i in 1:max_iter) {
    c <- (a + b) / 2
    if (abs(f(c)) < tol || (b - a) / 2 < tol) {
      return(list(root = c, value = f(c), iterations = i))
    }
    if (f(a) * f(c) < 0) {
      b <- c
    } else {
      a <- c
    }
  }
  warning("Maximum iterations reached without convergence")
  return(list(root = c, value = f(c), iterations = max_iter))
}

# Example: Find root of f(x) = x^3 - x - 2 on [1, 2]
f <- function(x) x^3 - x - 2
result <- bisection_method(f, 1, 2)
print(result)

The bisection algorithm works by repeatedly halving the interval $[a, b]$ where the function $f(x)$ changes sign. At each step, you compute the midpoint $c = (a + b) / 2$ . If $f(c)$ is close enough to zero (within the specified tolerance), or the interval has become sufficiently small, the process stops and $c$ is returned as the root. Otherwise, you check which subinterval, $[a, c]$ or $[c, b]$ , contains the sign change and repeat the process on that subinterval. This method is guaranteed to converge if the function is continuous and the initial interval brackets a root (that is, $f(a)$ and $f(b)$ have opposite signs).

Key steps in the bisection method:

Start with a continuous function $f(x)$ and an interval $[a, b]$ such that $f(a)$ and $f(b)$ have opposite signs;
Calculate the midpoint $c = (a + b) / 2$ ;
Check if $|f(c)|$ is less than your chosen tolerance, or if $(b - a) / 2$ is less than the tolerance;
If so, return $c$ as the root and stop;
If not, determine which subinterval contains the sign change:
- If $f(a) * f(c) < 0$ , set $b = c$ ;
- Otherwise, set $a = c$ ;
Repeat the process until the root is found or the maximum number of iterations is reached.

This method has linear convergence and may be slower than other iterative techniques, but its reliability makes it valuable for a wide range of root-finding problems. The provided R code demonstrates this process, checking the sign and tolerance at each iteration and returning the root, function value, and number of iterations when done.


              1234
            
# Using uniroot() to solve f(x) = cos(x) - x numerically on [0, 1]
f <- function(x) cos(x) - x
uniroot_result <- uniroot(f, lower = 0, upper = 1)
print(uniroot_result)

The uniroot() function in R provides a convenient way to numerically solve equations of the form $f(x) = 0$ within a specified interval. When you run uniroot(), it returns a list containing the approximate root, the function value at that root, and the number of iterations used.

While uniroot() is efficient and easy to use, it requires that the function changes sign over the interval; otherwise, it will produce an error. Additionally, uniroot() is not suitable for finding multiple roots in a single call or for handling discontinuous functions. You should always check that your interval brackets a root and that the function is continuous over that interval to avoid misleading results.

Var allt tydligt?

Tack för dina kommentarer!

Avsnitt 2. Kapitel 2

Fråga AI

Fråga vad du vill eller prova någon av de föreslagna frågorna för att starta vårt samtal

Suggested prompts:

Can you explain how the bisection method compares to the Newton-Raphson method in practice?

What are some common pitfalls when using the bisection method?

How can I choose a good interval [a, b] for root-finding methods?

Svep för att visa menyn

Common iterative techniques include the bisection method and the Newton-Raphson method:

The bisection method is a robust and simple approach that requires only the function and an interval where the function changes sign;
The Newton-Raphson method uses tangents and requires the derivative of the function, often converging more quickly but being more sensitive to initial guesses and function behavior.


              123456789101112131415161718192021222324
            
# Bisection method for finding a root of f(x) = 0
bisection_method <- function(f, a, b, tol = 1e-7, max_iter = 100) {
  if (f(a) * f(b) >= 0) {
    stop("Function must change sign on [a, b]")
  }
  for (i in 1:max_iter) {
    c <- (a + b) / 2
    if (abs(f(c)) < tol || (b - a) / 2 < tol) {
      return(list(root = c, value = f(c), iterations = i))
    }
    if (f(a) * f(c) < 0) {
      b <- c
    } else {
      a <- c
    }
  }
  warning("Maximum iterations reached without convergence")
  return(list(root = c, value = f(c), iterations = max_iter))
}

# Example: Find root of f(x) = x^3 - x - 2 on [1, 2]
f <- function(x) x^3 - x - 2
result <- bisection_method(f, 1, 2)
print(result)

Key steps in the bisection method:

Start with a continuous function $f(x)$ and an interval $[a, b]$ such that $f(a)$ and $f(b)$ have opposite signs;
Calculate the midpoint $c = (a + b) / 2$ ;
Check if $|f(c)|$ is less than your chosen tolerance, or if $(b - a) / 2$ is less than the tolerance;
If so, return $c$ as the root and stop;
If not, determine which subinterval contains the sign change:
- If $f(a) * f(c) < 0$ , set $b = c$ ;
- Otherwise, set $a = c$ ;
Repeat the process until the root is found or the maximum number of iterations is reached.


              1234
            
# Using uniroot() to solve f(x) = cos(x) - x numerically on [0, 1]
f <- function(x) cos(x) - x
uniroot_result <- uniroot(f, lower = 0, upper = 1)
print(uniroot_result)

Var allt tydligt?

Tack för dina kommentarer!

Avsnitt 2. Kapitel 2