Chapter 4
-use fixed point analysis to find the root of a function in one variable
-the problem: find an s on the interval [a,b] such that s=g(s) whenever f(s)=0, where s is called the fixed point
-If for all x in the interval I g(x) is in I, and g(x) is continuous, then g(x) has at least one fixed point in I
-If for all x in the interval I g(x) is in I, and |g'(x)|<=L<1, for all x in I, then there exists a unique s such that g(s)=s.
-Newton's Method: g(x)=x-f(x)/f'(x) or xn+1=xn-f(xn)/f'(xn) for n=0,1,...
-Let f"(x) be continuous and f'(x) does not=0 in some open interval containing s, where f(s)=0. Then there exists an E>0 such that Newton's Method is quadratically convergent whenever |x0-s| is less than E
-Newton's Method in 2 variables: f(x,y)=0 and g(x,y)=0, solve for s and t such that f(s,t)=0 and g(s,t)=0
-first approximate s and t with x0 and y0 and take Taylor's expansion about (x0,y0):
-substitute (s,t) for (x,y) in the equations
-suppose (s-x0)2, (s-x0)(t-y0), and (t-y0)2 are small with respect to (s-x0) and (t-y0) and neglect Rf(s,t) and Rg(s,t)
-so solve for s and t
-let (x1,y1) be the solutions, the better approximations for s and t, then:
-an equivalent way of writing this is the matrix form J0(x1-x0)=-F(x0)
-If c0=[u0 v0]T is the solution of J0(x)=-F(x0), then x1=x0+c0 is an updated estimate to (s,t)
-x1=x0-J0-1F(x0) -> xi+1=xi-Ji-1F(xi), i=0,1,2,...
f(x,y)=f(x0,y0)+fx(x0,y0)(x-x0)+fy(x0,y0)(y-y0)+Rf(x,y)
g(x,y)=g(x0,y0)+gx(x0,y0)(x-x0)+gy(x0,y0)(y-y0)+Rg(x,y)
where Rf(x,y)=[fxx(alp,bet)(x-x0)2+2fxy(alp,bet)(x-x0)(y-y0)+fyy(alp,bet)(y-y0)2]/2
where (alp,bet) is a mean value point, a point on the line segment joining (x,y) and (x0,y0)
0=f(x0,y0)+fx(x0,y0)(x-x0)+fy(x0,y0)(y-y0)
0=g(x0,y0)+gx(x0,y0)(x-x0)+gy(x0,y0)(y-y0)
fx(x0,y0)(x1-x0)+fy(x0,y0)(y1-y0)=-f(x0,y0)
gx(x0,y0)(x1-x0)+gy(x0,y0)(y1-y0)=-g(x0,y0)
where x0=[x0 y0]T, x1=[x1 y1]T, F(x0)=[f(x0,y0) g(x0,y0)]T and J0 is the Jacobian matrix (it plays the role of the derivative)
-Newton's Method in Several Variables: the problem of simultaneously solving a system of n non-linear equations in n unknowns. Let x1,x2,...xn be real variables and let fi(x1,x2,...xn)be a real function for each i, 1<=i<=n.
-Want to find s1,s2,...sn such that fi(s1,s2,...sn)=0 simultaneously for each 1<=i<=n
-Let x=(x1,x2,...xn) be a vector of n variables, for each i, fi(x1,x2,...xn)=fi(x), also let F(x)=[f1(x) f2(x)...fn(x)]T
-Want to find a vector s=(s1,s2,...sn) such that F(s)=0, where 0 is the zero vector
-construct a vector valued function
-example: given any F(x) one choice would be g(x)=x+AF(x), where A is a nonsingular nxn matrix
-The fixed point iteration is xk+1=g(xk)
-Let R be a region in Rn such that x=(x1,x2,...xn) belongs to R if and only if a1<=x1<=b1, a2<=x2<=b2,...,an<=xn<=bn, where ai, bi 1<=i<=n are specified real numbers
-Let h=(h1,h2,...hn)contained in Rn. The derivative of g at x is defined to be the (nxn)matrix Ax that for all eps >0 there exists a del >0 such that
-Ax=g'(x)=J(x), the Jacobian matrix whose (i,j)th element is (del*gi(x))/del*xj
-xn+1=xn-J(xn)-1F(xn), n>=0
-inverses are hard to compute, so solve by defining zn+1=xn+1-xn, solve J(xn)zn+1=-F(xn) for zn+1, then find xn+1 by xn+1=zn+1+xn
g(x)=[g1(x1,x2,...xn) g2(x1,x2,...xn)...gn(x1,x2,...xn)]T
such that if g(s)=s, then F(s)=0
||g(x+h)-g(x)-Axh||< eps*||h||, whenever 0<||h||< del