Heath - Scientific Computing (523150), страница 50
Текст из файла (страница 50)
NONLINEAR EQUATIONSIn some cases, the nonlinear solver may failto converge or may converge to a point otherthan a solution. When this happens, try toexplain the reason for the observed behavior.Also note the convergence rate attained, and ifit is slower than expected, try to explain why.(a)x1 + x2 (x2 (5 − x2 ) − 2) = 13,x1 + x2 (x2 (1 + x2 ) − 14) = 29,= Xk + A−1 (I − AXk ).But A−1 is what we are trying to compute, soinstead we use the current approximation toA−1 , namely Xk .
Thus, the iteration schemetakes the formXk+1 = Xk + Xk (I − AXk ).(a) If we define the residual matrixstarting from x1 = 15, x2 = −2.(b)Rk = I − AXkx21 + x22 + x23x1 + x2x1 + x3= 5,= 1,= 3,√starting from√x1 = (1 + 3 )/2, x2 = (1 −√3 )/2, x3 = 3 .(c)√√=Ek = A−1 − Xk ,show thatRk+1 = Rk20,starting from x1 = 1, x2 = 2, x3 = 1, x4 = 1.(d )(b) Write a program to compute the inverseof a given input matrix A using this iterationscheme. A reasonable starting guess is to takeX0 =x110x1 /(x1 + 0.1) + 2x22==0,0,starting from x1 = 1.8, x2 = 0.(e)104 x1 x2e−x1 + e−x2==1,1.0001,starting from x1 = 0, x2 = 1.5.17 Newton’s method can be used to compute the inverse of a nonsingular n × n matrixA. If we define the function F : Rn×n → Rn×nbyF (X) = I − AX,where X is an n × n matrix, then F (X) = Oprecisely when X = A−1 .
Since F 0 (X) =−A, Newton’s method for solving this equation has the form0−1Xk+1 = Xk − [F (Xk )]and Ek+1 = Ek AEk ,from which we can conclude that the convergence rate is quadratic, despite using only anapproximate derivative.x1 + 10x2 = 0,5 (x3 − x4 ) = 0,(x2 − x3 )2 = 0,10 (x1 − x4 )2and the error matrixF (Xk )AT.kAk1 · kAk∞Test your program on a few randomly chosen matrices and compare its accuracy and efficiency with conventional methods for computing the inverse, such as LU factorization orGauss-Jordan elimination.5.18 Newton’s method can be used to compute an eigenvalue λ and corresponding eigenvector x of an n × n matrix A.
If we definethe function f : Rn+1 → Rn+1 byAx − λxf (x, λ) =,xT x − 1then f (x, λ) = o precisely when λ is an eigenvalue and x is a corresponding normalizedeigenvector. SinceJf (x, λ) =A − λI2xT−x,0COMPUTER PROBLEMSNewton’s method for solving this equation hasthe form xk+1xks=+ k ,λk+1λkδkTwhere [ sksystemδk ]is the solution to the linear A − λk I −xksk2xTk0δkAxk − λk xk=−.xTk xk − 1181Write a program to compute an eigenvalueeigenvector pair of a given input matrix A using this iteration scheme. A reasonable starting guess is to take x0 to be an arbitrarynormalized nonzero vector (i.e., xT0 x0 = 1)and take λ0 = xT0 Ax0 (why?). Test yourprogram on a few randomly chosen matricesand compare its accuracy and efficiency withthose of conventional methods for computing asingle eigenvalue-eigenvector pair, such as thepower method.
Note, however, that Newton’smethod does not necessarily converge to thedominant eigenvalue.182CHAPTER 5. NONLINEAR EQUATIONSChapter 6Optimization6.1Optimization ProblemsWe now turn to the problem of determining extreme values, or optimum values (maximaor minima), that a given function has on a given domain. More formally, given a functionf : Rn → R, and a set S ⊆ Rn , we seek x ∈ S such that f attains a minimum on S at x, i.e.,f (x) ≤ f (y) for all y ∈ S. Such a point x is called a minimizer , or simply a minimum, off . Since a maximum of f is a minimum of −f , it suffices to consider only minimization.The objective function, f , may be linear or nonlinear, and it is usually assumed tobe differentiable.
The constraint set S is usually defined by a system of equations orinequalities, or both, that may be linear or nonlinear. A point x ∈ S that satisfies theconstraints is called a feasible point. If S = Rn , then the problem is unconstrained .General continuous optimization problems have the formmin f (x)xsubject to g(x) = o and h(x) ≤ o,where f : Rn → R, g: Rn → Rm , and h: Rn → Rk . Optimization problems are classified bythe properties of the functions involved. For example, if f , g, and h are all linear, then wehave a linear programming problem.1 If any of the functions involved are nonlinear, then wehave a nonlinear programming problem. Important subclasses of the latter include problemswith a nonlinear objective function and linear constraints, or a nonlinear objective functionand no constraints. We will focus mainly on optimization problems in one dimension andunconstrained problems in n dimensions.We will not address discrete optimization problems—such as integer programming, inwhich the variables can take on only integer values—because such problems usually requirecombinatorial rather than numerical techniques.
In addition to traditional combinatorialtechniques, such as branch-and-bound, there has been a great deal of research in recentyears on new approaches to discrete optimization, such as simulated annealing and geneticalgorithms, but these topics are beyond the scope of this book.1The use of the term programming in optimization has nothing to do with computer programming, butinstead refers to planning activities in the sense of operations research or management science.183184CHAPTER 6. OPTIMIZATIONExample 6.1 Optimization Problems. Optimization problems arise in many areas ofscience, engineering, economics, and business.
One might want to minimize the weight ofa structure subject to a constraint on its strength, or maximize its strength subject to aconstraint on its weight (note the duality here, which is common in optimization). Onemight want to minimize the cost of a diet subject to nutritional constraints, and so on.A concrete example is to minimize the surface area of a cylinder subject to a constrainton its volume:min f (x1 , x2 ) = 2πx1 (x1 + x2 )x1 ,x2subject to g(x1 , x2 ) = πx21 x2 = V,where x1 and x2 are the radius and height of the cylinder, respectively, and V is the requiredvolume.
The solution to this problem minimizes the amount of material required to makean appropriate container for the given quantity of liquid. (A sphere with the given volumewould require even less surface area but would not make a practical container.)6.1.1Local versus Global OptimizationA function f has a global minimum at a feasible point x∗ if f (x∗ ) ≤ f (x) for all feasiblepoints x. We say that f has a local minimum at a feasible point x∗ if f (x∗ ) ≤ f (x) forall feasible points x in a neighborhood of x∗ . These concepts are illustrated for a onedimensional unconstrained problem in Fig.
6.1............................................................................................................................................................ .............................................. ........ .........↑local minimum↑global minimumFigure 6.1: Local and global minima.Finding the global minimum of a function, or even verifying that a point is the globalminimum after it has been found, is a very difficult problem unless the function has specialproperties. Most optimization methods are designed to find a local minimum, which mayor may not be the global minimum. In general, there is no foolproof way to guarantee thata specific local minimum, or in particular the global minimum, will be found.
Usually thebest one can do is to start the iterative solution process with an initial guess as close aspossible to the desired minimum point.For many purposes, a local minimum of a function may suffice. If the global minimumis desired, however, one way to try to find it is to use several different, widely separatedstarting points. If they all produce the same result, then there is a good chance that theglobal minimum has been found. If they produce different results, then taking the lowest6.1. OPTIMIZATION PROBLEMS185of the local minima is the best one can do; but there may still be other unexplored regionswith even lower values.Global optimization for general problems is an active area of research, but with fewironclad results.
For special categories of problems, however, global optimization is muchmore tractable. For example, global solutions to linear programming problems, or moregenerally convex programming problems, are routinely obtained by very efficient methods.6.1.2Relationship to Nonlinear EquationsOptimization is related to finding zeros of functions because extrema of smooth functionscorrespond to zeros of their derivatives. For example, if x∗ minimizes an unconstrainedfunction f : Rn → R, then the partial derivative of f with respect to each variable xi is zero,which means that x∗ is a solution to the system of equations ∇f (x) = o.
[Recall thatthe gradient of f evaluated at x, denoted by ∇f (x), is a vector-valued function whose ithcomponent function is the partial derivative of f with respect to xi , ∂f (x)/∂xi .]The converse is not true, however: a solution to the system of nonlinear equations∇f (x) = o, which is known as a stationary point or critical point, may be a minimum,a maximum, or neither (e.g., a saddle point) of f . Nevertheless, many methods for optimization are based on seeking a critical point of a gradient function, which is a system of(generally nonlinear) equations. Any candidate solution found by such a method should bechecked for optimality.A critical point x of an unconstrained objective function f can be checked for optimalityby considering the Hessian matrix Hf (x) of second partial derivatives of f ,{Hf (x)}ij =∂ 2 f (x),∂xi ∂xjevaluated at x.
If f has continuous second partial derivatives, the Hessian matrix Hf (x)is symmetric. At a critical point x, where ∇f (x) = o, if Hf (x) is••••Positive definite, then x is a minimum of f .Negative definite, then x is a maximum of f .Indefinite, then x is a saddle point of f .Singular, then a variety of behavior can occur.There are a number of ways to test a symmetric matrix for positive definiteness.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
