Iterative Methods

2 Key excerpts on "Iterative Methods"

• 

  eBook - ePub

  Nonlinear Inverse Problems in Imaging

  • Jin Keun Seo, Eung Je Woo(Authors)
  • 2012(Publication Date)
  • Wiley

    (Publisher)

  Chapter 5 Numerical Methods

  Quantitative analyses are essential elements in solving forward and inverse problems. To utilize computers, we should devise numerically implementable algorithms to solve given problems, which include step-by-step procedures to obtain final answers. Formulation of a forward as well as an inverse problem should be done bearing in mind that we will adopt a certain numerical algorithm to solve them. After reviewing the basics of numerical computations, we will introduce various methods to solve a linear system of equations, which are most commonly used to obtain numerical solutions of both forward and inverse problems. Considering that most forward problems are formulated by using partial differential equations, we will study numerical techniques such as the finite difference method and finite element method. The accuracy or consistency of a numerical solution as well as the convergence and stability of an algorithm to obtain the solution need to be investigated.

  5.1 Iterative Method for Nonlinear Problem

  Recall the abstract form of the inverse problem in section 4.1, where we tried to reconstruct a material property P from knowledge of the input data X and output data Y using the forward problem (4.1 ). It is equivalent to the following root-finding problem:

  where X and Y are given data.

  We assume that both the material property P and F(P, X) are expressed as vectors in N-dimensional space . Imagine that P* is a root of G(P) = 0 and P0 is a reasonably good guess in the sense that P0 + ΔP = P* for a small perturbation ΔP. From the tangent line approximation, we can approximate

  where J(P0 ) denotes the Jacobian of G(P) at P0 . Then, the solution P* = P0 + ΔP can be approximated by

  The Newton–Raphson algorithm is based on the above idea, and we can start from a good initial guess P0 to perform the following recursive process:

  5.1

  The convergence of this approach is related to the condition number of the Jacobian matrix J(P*). If J(P*) is nearly singular, the root-finding problem G(P) = 0 is ill-posed. According to the fixed point theorem, the sequence P

  n

  converges to a fixed point P* provided that Φ(P): = P − [J(P)]−1 G(P

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Numerical Analysis

  An Introduction

  • Timo Heister, Leo G. Rebholz, Fei Xue(Authors)
  • 2019(Publication Date)
  • De Gruyter

    (Publisher)

  5Solving nonlinear equations

  There should be no doubt that there is a great need to solve nonlinear equations with numerical methods. For most nonlinear equations, finding an analytical solution is impossible or very difficult. Just in one variable, we have equations such as

  ex

  = x 2 which cannot be analytically solved. In multiple variables, the situation only gets worse. The purpose of this chapter is to study some common numerical methods for solving nonlinear equations. We will quantify how they work, when they work, how well they work, and when they fail.

  5.1Convergence criteria of Iterative Methods for nonlinear systems

  This section will develop and discuss algorithms that will (hopefully) converge to solutions of a nonlinear equation. Each method we discuss will be in the form of: Step 0: Guess at the solution with x 0 (or two initial guesses x 0 and x 1 ) Step k : Use x 0 , x 1 , x 2 , . . . ,

  xk

  −1 to generate a better approximation

  xk

  These algorithms all build sequences

  {

  x k

  }

  k = 1

  ∞

  =

  {

  x 0

  ,

  x 1

  ,

  x 2

  , ...

  }

  which hopefully will converge to a solution x ∗ . As one might expect, some algorithms converge quickly, and some converge slowly or not at all. It is our goal to find rigorous criteria for when the discussed algorithms converge, and to quantify how quickly they converge when they are successful. Although there are several ways to determine how an algorithm is converging, it is typically best mathematically to measure error in the k th iteration (

  ek

  = |

  xk

  − x ∗ |), that is, the error is the distance between

  xk

  and the solution. Once this is sufficiently small, the algorithm can be terminated, and the last iterate becomes the solution.

  We now define the notions of linear, superlinear, and quadratic convergence.

  Definition 31. Suppose an algorithm generates a sequence of iterates {x 0 , x 1 , x 2 , . . .} which converges to x ∗

  Sign up to read

  Learn more about book