### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# NUMERICAL ANALYSIS Math 105A

UCI

GPA 3.73

### View Full Document

## 53

## 0

## Popular in Course

## Popular in Mathematics (M)

This 28 page Class Notes was uploaded by Adam Crona on Saturday September 12, 2015. The Class Notes belongs to Math 105A at University of California - Irvine taught by Staff in Fall. Since its upload, it has received 53 views. For similar materials see /class/201865/math-105a-university-of-california-irvine in Mathematics (M) at University of California - Irvine.

## Reviews for NUMERICAL ANALYSIS

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/12/15

Chapter 6 Computer Algebra 61 Matlab s Symbolic Toolbox Matlab s Symbolic Toolbox is a collection of functions that provide access to some of Maple s functionality Using this toolbox one can create sym objects which represent expressions and perform symbolic operations on them such as differentiation integration or analytical solution techniques for equations 611 Creating Symbolic objects The sym function creates a new Matlab object that represents an expression similar to an expression in Maple lt accepts as an argument a string repre senting the expression and returns an object Whose value is that expression An optional second argument can be used to set properties of the ex pression such as whether the expression is assumed to be a real number or a positive number Instead of a string one may pass a matrix to sym in which case a sym bolic representation of the matrix is created An optional second argument indicates how the oating point entries are to be represented symbolically The argument f is used to create a oating point representation r for a rational representation the default d for decimal and e for estimate error which implies I but also provides an estimate of the error in the rational approximation gtgt myexprsym x myexpr 201 gtgt myexpr2sym xquot2 myexpr2 xquot2 gtgt sym13 ans 13 gtgt sym13 f ans 15555555555555 2quot2 gtgt sym13 d ans 33333333333333331482961625624739 gtgt sym13 e ans 13eps12 The syms command is used as a shortcut for creating several symbolic variables The arguments to syms are each passed to sym For each argu ment7 a new object is created with the same name as the argument and its value equal to the symbolic variable of that name syms cannot be used to create symbolic objects representing arbitrary expressions With no argu ments7 syms lists all symbolic variables 202 612 Calculus The Symbolic toolbox offers a number of functions for performing common tasks from calculus o The diff function computes a derivative of a symbolic object with respect to a given variable Similarly the int function computes an inde nite integral of a symbolic object or integrates an expression over a speci ed interval The taylor function computes the Taylor series of its rst argument to a speci ed number of terms It can also compute the series with respect to a given variable if one is not apparent from the expression itself The limit function computes the limit of an expression as a given variable approaches a given value It can also compute limits as a variable approaches in nity or compute onesided limits Given a vector valued symbolic object f and a vector of variables x jacobian computes the Jacobian of f with respect to x The following code illustrates the use of these functions gtgt xsym x gtgt taylorexpx ans 1x12xquot216xquot3124xquot41120xquot5 203 gtgt limit1xx0 left ans inf gtgt syms y gtgt jacobian expxy xquot2y X yl ans yexp xy xexpxy 2xy xquot2 613 Linear Algebra The following functions many of which are familiar work with symbolic matrices o diag creates a symbolic diagonal matrix or extracts a diagonal of a symbolic matrix 0 triu returns the upper triangular part of a symbolic matrix 0 tril returns the lower triangular part of a symbolic matrix 0 inv computes the inverse of a symbolic matrix 0 det computes the determinant of a symbolic matrix 0 rank computes the rank of a symbolic matrix 0 rref computes the reduced row echelonn form of a symbolic matrix null computes a basis for null space of a symbolic matrix A ie the set of vectors X for which Ax O o colspace computes a basis for the column space of A ie the set of vectors y for which y Ax for some vector x o eig computes the eigenvalues andor eigenvectors of a symbolic ma trix 204 svd computes the singular value decomposition of a symbolic matrix Singular vectors can only be computed for matrices with numeric val ues jordau computes the Jordan canonical form of a symbolic matrix poly computes the characteristic polynomial of a symbolic matrix A ie detI 7 A expm computes the matrix exponential of a symbolic matrix A ie expA 614 Simpli cation of Expressions The following functions may be used to rearrange expressions with the goal of simplifying them They accept an expression or a matrix of expressions simplify uses a variety of techniques to try to reduce the size of an expression expand rewrites an expression as a sum of terms distributing whenever possible collect rewrites an expression as a polynomial in given variables simple not only simpli es an expression but indicates the sequence of steps used to simplify it numden converts an expression to a rational form horner converts a symbolic polynomial to its nested Horner repre sentation subexpr rewrites an expression in terms of common subexpressions subs substitutes variables in an expression with values obtained from the workspace where subs is called gtgt simplifycos x quot2sinx quot2 ans 205 gtgt expand x1 EC1 gtgt z4 gtgt subsexpz ans 545982 615 Solution of Equations Maple s functions for solving equations or systems of equations are also available 0 solve accepts a list of equations which can be strings or expressions involving symbolic variables and an optional list of unknowns and solves the equations for the unknowns o dsolve is similar to solve for differential equations 0 finverse returns an f 1y for a given function y An optional second argument speci es the independent variable of f the default is x o compose computes the composition of two expressions gtgt uvsolve uv1 uv0 u v 12 206 gtgt Ssolve uv1 uv0 u V S 11 1x1 sym v 1x1 sym gtgt Su ans 12 gtgt dsolve D2yy y01 Dy01 ans costsint gtgt composeexpxsinx ans expsinx gtgt finverseexpX ans logx 616 Variable Precision Arithmetic Matlab can use Maple s variable precision arithmetic vpa numerically eval uates each element of its argument using variable precision oating point arithmetic with D decimal digits of accuracy where D is the current value returned by digits digits with no arguments returns the current preci sion lt accepts an integer argument which becomes the new precision gtgt digits 207 Digits 32 gtgt vpa13 ans gtgt digits16 gtgt vpa13 ans 3333333333333333 617 Data Conversion Often it is desirable to convert between data used in symbolic operations and data used with Matlab s own functions 0 double converts a symbolic matrix to an ordinary Matlab matrix It must not contain any symbolic variables except for eps poly2sym and sym2poly convert between a symbolic polynomial in a given variable default x to Matlab s representation of a polyno mial a row vector of the coef cients 0 char converts a symbolic expression to a string 618 Basic Operations on Symbolic Objects o findsym returns a list of independent variables in a given expression 0 pretty formats an expression for more readable display 0 latex ccode and fortran return LaTeX C and FORTRAN repre sentations respectively of a given expression 208 619 Using Maple Within Matlab The Symbolic toolbox operates using the Maple kernel In addition to the toolbox routines previously discussed Maple statements can be executed with Matlab usin the following functions 0 maple evaluates a given Maple statement 0 mfun evaluates a given Maple function with numeric arguments o mfunlist lists all available Maple functions 0 mhelp displays Maple help on a given topic 0 procread loads a given Maple procedure for later use These features require a license to use Matlab s Extended Symbolic toolbox 62 Symbolic Operations with Maple 63 Exercises 209 Chapter 5 Elementary Signal Processing 51 Mathematical Preliminaries 511 Integral Transforms Integral transforms such as the Fourier transform and the Laplace trans form7 play a key role in the solution of differential equations and serve as the foundation for signal processing Both Matlab and Maple provide an array of functions for working with these and other transforms 512 The Fourier transform The Fourier transform of a function x de ned for all real values of w by the integral formula 1 X from fw iwe fwdw 700ltwltoo 51 The Fourier transform of x fw can be viewed as a function of w the frequency Thus f is regarded as a superposition of waves of all frequencies a each with amplitude and phase shift argfw7 where for any complex number 2 argz is the angle that 2 makes in the complex plane with the real ax1s 189 The Inverse Fourier Transform The inverse Fourier transform of w is given by the similar integral formula 1 00 w 7 ewz w dw 700 lt w lt 00 52 f gt m m f gt lt gt Properties of Fourier Tranforms One of the most useful properties of the Fourier transform is the fact that given the Fourier transform fw of a function at computing the Fourier transform of f w is very simple 7 1 00 64 w w NM 7 mm NW 1 X 4 7mm 7 iw72we 53 WWW In general we have the property that the Fourier transform of dnfdw is f This provides a means of transforming a differential equation into a much simpler algebraic equation It follows from the fact that the exponential function is an eigenfunction of the differentiation operator with the eigenvalue based on the frequency Convolution Often it is desirable to compute the inverse transform hw of the product of two known Fourier transforms fw w For instance may be a signal and w may be a lter that damps or even removes certain frequencies Fortunately this inverse transform is simple to compute in terms of the inverse transforms of and w namely at and gw hltwgt w emfltwgt ltwgtdw 1 00 ltgt0 7 i was from i 2W1me fM Xf 93gtd3dw 54 i 00 9yw emziygtfwdwdy 27 7ltgto foo gwmwy 190 hx is known as the convolution of x and A similar rule holds true for the Fourier transform of the product of two functions of x Other Properties The following table lists some known Fourier transforms m 1 m gta 513 Fourier Series A function de ned on an interval can be represented by its Fourier series7 a superposition of waves of integer valued frequencies For the case of a function x de ned on 027r7 we have the series 1 X iwx A ma w e m 55 which converges to x for every x if x is continuous and 27r periodic We see that the above series is a discrete analogue of the inverse Fourier transform given earlier The Discrete Fourier Transform To obtain the coef cients w of the Fourier series for x7 for all integers u we use the discrete Fourier transform 1 27f iiwx MW e mm 56 which can be seen to closely resemble the formula for the continuous Fourier transform presented earlier 191 Trigonometric Interpolation Often a function x is a grid function represented by a list of function values often obtained experimentally at speci ed points called grid points In this case the Fourier series coef cients can be computed by approximating the integral de ning with a sum In the case of N1 equally spaced points with spacing h 27rN1 we have h N iiwj 7 fw jzte h gh wiiN2N2 57 The approximate coe icients w are the exact Fourier coef cients of the Fourier interpolant of x which agrees with x at the grid points The Fast Fourier Transform The formula for computing each Fourier series coe icient of x re quires ON operations where N is the number of grid points Since there are ON coef cients in the Fourier interpolant the process of computing all of them requires ON2 operations The Fast Fourier Transform is a method that allows all of the coef cients to be computed in ONlog N time a huge difference for large values of N 514 The Fourier Sine and Cosine Transforms Partial differential equations with various boundary conditions have given rise to variations on the Fourier transform For Dirichlet boundary conditions where the solution to a PDE vanishes on the boundary of the problem s domain the Fourier sine transform is useful mo fxsinwxds 58 0 with corresponding inversion formula fwgt w m sinwwdwr 59 For Neumann boundary conditions Where the deriviative of the solution to the PDE vanishes on the boundary of the problem s domain the Fourier 192 cosine transform is useful to w fwgt coswwds 510 with corresponding inversion formula fw wfsltwgtcoswwdwr 511 515 Fourier Transforms in Higher Dimensions The Fourier transform generalizes directly to higher dimensions lf fx is a function of an n vector x then the Fourier coe icient fw where w is a frequency represented by an n vector can be computed as follows A 1 iiwx m we fltxgtdx 512 where represents the inner product of two vectors A similar formula yields the inverse transform 516 The Laplace Transform While the Fourier transform is used to represent a function of spatial vari ables as a collection of waves the Laplace transform is used to construct such a representation for a function of time Given a function 3t de ned for t 2 0 the Laplace transform Lyt is de ned by Lytgtl Yltsgt manwow 513 The Inverse Laplace Transform The inverse Laplace transform ons is the function 3t such that Lyt Ys Like the Fourier transform there is an integral formula for the inverse transform but it requires complex integration theory to evaluate lnstead 3t is determined by expressing Ys as a combination of functions whose inverse transforms are already known 193 Properties of the Laplace Transform The following table lists some known Laplace transforms The Laplace Transform of a Derivative As with Fourier transforms the Laplace transform of a derivative of 3t is easy to compute in terms of its transform Ys Using integration by parts repeatedly we obtain L Sny8gt 7 Sn71y0gt i y 1gt0 514 Thus a differential equation whose solution depends on time can be trans formed into an algebraic equation using the Laplace Transform 517 Other Integral Transforms The Hilbert Transform of a function ft is l 00 t Fs 1 ffldt 515 The Mellm Transform of a function fw is Fs Am f5551 d5 516 194 The Hankel Transform of a function ft is ms Am mmet dt where J1 is the Bessel function of the V th kind 52 Matlab s Signal Processing Toolbox The Signal Processing toolbox is a collection of functions for working with signals It allows users to transform signals design and use various lters perform statistical analysis on signals and perform various other operations concerning signals It also provides audio support For a complete list of functions type help signal at the Matlab prompt Basic Signal Processing Functions abs returns the amplitide of each frequency component of a signal angle returns the phase shift of each frequency component of a signal conv computes the convolution of two given vectors fft ifft compute the Fast Fourier Transform and Inverse Fast Fourier Transform of a vector dct idct compute the Discrete Fourier Cosine Transform and Inverse Discrete Fourier Cosine Transform respectively dftmtx returns a matrix of a given size that can be used to compute the Fourier transform of a vector by matrix vector multiplication hilbert czt compute the Hilbert and Chirp Z transform of a vector filter applies a lter described by two vectors to a given vector fftfilt lters a given vector with a given FIR lter using the FFT for greater e iciency FIR nite impluse response lter design IIR in nite impulse response lter design sound plays a vector as sound 195 o WAV support 0 AU support 53 Maple s Inttrans Package Maple offers a package inttrans for computing integral transforms of ex pressions o fourier computes the Fourier transform of a function 0 invfourier computes the inverse Fourier transform of a function 0 fouriercos computes the Fourier cosine transform of a function 0 fouriersin computes the Fourier sine transform of a function 0 laplace computes the Laplace transform of a function and invlaplace the inverse transform 0 hankel computes the Hankel transform of a function which is based on Bessel functions 0 hilbert computes the Hilbert transform of a function 0 mellin computes the Mellin transform of a function and invmellin the inverse transform 0 addtable allows the user to make a transform of a function known to Maple o savetable saves a table of known transforms to a le Matlab s Symbolic Toolbox o fourier ifourier compute the Fourier and inverse Fourier transform of a function 0 laplace ilaplace comptue the Laplace and inverse Laplace trans form of a function 196 o ztrans and iztrans compute the Z transform and inverse Z transform of a function that depends on an independent integer valued variable 71 The Z transform of a function fn is Fe 2277701 518 54 Matlab s Wavelet Toolbox The Wavelet toolbox provides functions for decomposing signals into wavelets Several wavelet families are supported such as Haar Daubechies Gaussian and Meyer wavelets The wavemenu command launches a GUI for analyzing signals using wavelets Alternatively the following commands and others may be used 0 cwt computes continuous wavelet coef cients 0 dwt and idwt compute and invert the single level discrete 1 d wavelet transform dwt2 and idwt2 are the 2 D analogues o wavedec and waverec provide multi level l D wavelet decomposition and reconstruction wavedec2 and waverec2 do the same for the 2 D case 55 Exercises H Suppose that you are representing a function f on the interval 027r using a vector f of N values obtained by evaluating f at N equally spaced points called gridpomts in the interval 0 2w Specif ically fj fjh j O1N 71 where h 27rn The Discrete Fourier Transform of f w represents f as a vector of N Fourier coef cients corresponding to N frequencies numbered from O to N 7 1 This discrete transform may easily be computed using a sum to approximate the integral used to compute each component of the Fourier series N71 A h WPEE Wm w01N71 519 70 197 10 Write a function that accepts a vector corresponding to function val ues as input and returns as output the discrete Fourier transform using 519 above The function should have the form function g dftf Hint use the exp function which takes the exponential of every ele ment of its argument For example gtgt exp0 exp1 ans ans 27183 gtgt exp 0 1 2 ans 10000 27183 73891 Also the constant 2 represents the imaginary unit V71 You may use 2 as a variable but this is not recommended since then you are no longer able to use 2 as the imaginary unit In 1965 Cooley and Tukey used the above representation 519 of the Fourier coe icients to obtain a much more e icient method of com puting the discrete Fourier transform the Fast Fourier Transform Assume N is a power of 2 and de ne the gridfunctions f8 and f0 as follows f8 is a gridfunction de ned using the even numbered grid points and grid values of f ie fab fzjy Similarly f0 is a gridfuction de ned using the odd numbered grid points and grid values of f ie foj f2j17 jqrqu 71 5m jQLHqN 71 ago 198 Then we have h N1 A iwjh W m jg 6 f h N21 h N1 2739 Z eiwzjhfzj 1 12 2 7Wlt231lgthf271 522 70 70 N21 N21 1 2h 7 1 7 2h 7 i 27 Z 6 2w2hf8gtj ugh 27 Z 6 2w2hf0gtj V 70 V 70 First assume that w lt N2 Then we obtain A 1 A 1 iwh A fw ife u 6 f0w 523 Otherwise we let I1 w N2 and obtain N21 N21 A 1 2h 7aN272h 1 iwh 2h 2 QN2j2h f0 i j 6 fa i6 E 3 6 f0 N21 N21 7 1 2h ijNh 772h 1 4 2h ijNh 772h 7 6 6 f5gt2 m 6 6 f0 N21 N21 1 2h 1 2h Z 22 2w32hf8gtj 2whE Z 22 2w32hf65j24gt V 70 V 70 N21 N21 1 2h 7m 1 7 2h im i 27 Z 6 2w2hf8gtj ugh 27 Z 6 2w2hf0gtj V 70 V 70 1 A 1 1 A yew ie Wow Thus the discrete Fourier transform of a function can be computed by splitting the set of function values into two sets the even numbered and odd numbered points computing the discrete Fourier transforms of those functions and then combining them appropriately Of course this decomposition stops when N is already 1 in which case computing the Fourier transform is quite trivial Write a function that performs the Fast Fourier transform This func tion may call itself Make sure that under the appropriate conditions 199 Jim Lambers IVIath 105A Summer Session I 2003 04 Lecture 5 Notes These notes correspond to Section 23 in the text Newton s Method In the previous lecture we developed a simple method bisection for approximately solving the equation f 1 0 Unfortunately this method while guaranteed to find a solution on an interval that is known to contain one is not practical because of the large number of iterations that are necessary to obtain an accurate approximate solution To develop a more effective method for solving this problem of computing a solution to f 1 0 we can address the following questions 0 Are there cases in which the problem to solve and if so how do we solve it in such cases 0 Is it possible to apply our method of solving the problem in these easy cases to more general cases In this course we will see that these questions are useful for solving a variety of problems For the problem at hand we ask whether the equation f 1 0 is to solve for any particular choice of the function Certainly if is a linear function then it has a formula of the form f 1 m1 a 1 where m and I are constants and m 7 0 Setting f 1 0 yields the equation m1 a 1 0 which can easily be solved for 1 to obtain the unique solution I 1 a i m We now consider the case where f is not a linear function Using Taylor s theorem it is simple to construct a linear function that approximates f 1 near a given point 10 This function is simply the first Taylor polynomial of with center 1390 P1 1 fU ol f39U olU 0 This function has a useful geometric interpretation its graph is the tangent line of at the point m f fol We can obtain an approximate solution to the equation f 1 0 by determining where the linear function P1 1 is equal to zero If the resulting value 11 is not a solution then we can repeat this procei approximating by a linear function near 1 and once again determining where this approximation is equal to zero The resulting algorithm is Newton s method which we now describe in detail Algorithm Newton s Method Let R gt R be a differentiable function The following algorithm computes an approximate solution 1 to the equation f 1 0 Choose an initial guess 10 for k 012 do if is suf ciently small then 1 return 1 end n1 if 1k1 is suf ciently small then J y n1 return 1 end end When Newton s method converges it does so very rapidly However it can be dif cult to ensure convergence particularly if f 1 has horizontal tangents near the solution Typically it is necessary to choose a starting iterate 1o that is close to As the following result indicates such a choice if close enough is indeed suf cient for convergence Theorem Convergence of Newton s Method Let f be twice continuously di erentiable on the interval 21 and suppose that fc 0 and f c 0 for some c 6 do Then there exists a 6 gt 0 such that Newton s Method applied to f 1 converges to c for any initial guess 10 in the interval 0 3 c 6 The Secant Method One drawback of Newton s method is that it is necessary to evaluate f 1 at various points which may not be practical for some choices of f The secant method avoids this issue by using a finite difference to approximate the derivative As a result f 1 is approximated by a secant line through two points on the graph of rather than a tangent line through one point on the graph Since a secant line is defined using two points on the graph of f 1 opposed to a tangent line that requires information at only one point on the graph it is nec to choose two initial iterates 10 and 11 Then in Newton s method the next iterate 12 is then obtained by computing the 1 value at which the secant line passing through the points 1of1o and 11f11 has a y coordinate of zero This yields the equation J J f r flt 0x24x044f00 11 10 which has the solution 12 J fU oW l f0 4 fm fU ol which can be rewritten follows fU olU l 0 fwo mgt mfJ391 fJ390 fJ390J391 J390 fwa m fwa m MUD391 fU oll fU oW l f0 f9 fU ol fofUn fofU o flfUD fofUb fm fU ol JDfU ll m m fm fU ol This leads to the following algorithm Algorithm Secant Method Let R gt R be a continuous function The following algorithm computes an approximate solution J to the equation f 1 0 Choose two initial guesses x0 and x1 for k 123 do if is suf ciently small then J return J end n1 M1 fm k Wt x if xk is suf ciently small then f J k return J end end Like Newton s method it is necessary to choose the starting iterate 0 to be reasonably close to the solution Convergence is not rapid that of Newton s Method since the secantline approximation of is not accurate the tangentline approximation employed by Newton s method Jim Lambers Math 105A Summer Session I 200304 Lecture 7 Notes These notes correspond to Section 26 in the text Zeros of Polynomials and Muller s Method Naturally any of the methods we have discussed for solving the equation x 0 can be applied to the case where x is a polynomial However we can take advantage of our knowledge of polynomials in order to use these methods as effectively as possible To that end we recall the following well known consequence of the Fundamental Theorem of Algebra that a polynomial pm with real or complex coefficients of degree n has the factorization k Mad1mW2 i1 where an is a nonzero constant the numbers 12 mk are the distinct roots of pm and the positive integers m1 m2 mk are the multiplicities of the roots satisfying the condition k 2 mi 7 n i1 It is important to note that the roots may be either real or complex even if the coefficients ofpm are real This factorization suggests an algorithm for computing not just one solution of pz 0 but all solutions at least in the case where all of the roots of pz are real The basic idea is to use one of our zero nding algorithms such as Newton s Method to nd one solution m1 and then divide pz by m 7 1 repeatedly in case the multiplicity of 1 is greater than one to obtain the factorization MMWMW where qz1 7 0 Then we can repeat this process on qm until all of the roots have been found This process is called de ation De ation however can be problematic because any inaccuracy in 1 contaminates the compu tation of the roots of qm so the last roots computed could be highly inaccurate One way around this difficulty is to compute approximate roots i1 i2 ik by de ation and then compute more accurate roots by applying Newton s Method directly to pz using these approximations as initial iterates Hornerls Method The simple structure of a polynomial allows us to construct a very ef cient algorithm for applying Newton s Method to a polynomial This structure is most effectively exploited by the following result Theorem Horner s Method Let 7L pz 2 am1 i0 be a polynomial of degree n If we de ne the constants b0 b1 1 by the recurrence relation bnan bkakbk1m0 kn71n7210 then WE 90 96mm be where n qm Zbizlil i1 is a polynomial of degree n 7 1 From this theorem we obtain 19900 507 Pmo 900 This leads to the following algorithm that serves as the essential component of Newton s Method applied to a polynomial Algorithm Horner s Method Let pz anz an1z 1 alz a0 be a polynomial of degree n and let mo 6 R The following algorithm computes y Mn and z pxo yan zan forkn71n721do yakymo zyzz0 end ya0y0 The value y is computed by applying Horner s Method to pz to obtain the quantity 0 described in the preceding theorem and z is computed by applying Horner s Method in the same way to the polynomial qz described in the theorem In both cases the coefficients 131192 are overwritten because only be is required As can be seen in the statement of the theorem the coefficients bn71 bn72 b1 obtained by applying Horner s Method to pz are the coefficients of qz which explains why the value of y is used to compute z in each iteration There are several good reasons to use Horner s Method for polynomial evaluation instead of the straightforward method of computing 1 2990 mm an71ni aim a0 directly 0 Fewer arithmetic operations are performed using Horner s Method so there is less computa tional expense 0 The computed result obtained using Horner s Method are signi cantly more accurate due to the fact that fewer operations are performed 0 Let zk be the kth iterate obtained using Newton s Method to compute a root ofpm Suppose that the constants bn71bn2 b2b1 obtained by applying Horner s Method to pz to compute pmk are retained rather than overwritten as in the preceding algorithm If the iterate zk is an approximate root ofpm then by the preceding theorem pz z However these constants are the coefficients of qm which implies that if M is a simple root of pz that is its multiplicity is one then de ation has already been accomplished in the course of computing pmk and we can immediately apply Newton s Method to qz to compute the remaining roots of It is easy to detect whether zk is a simple root of pm as this is the case if and only if pmk 7 O Horner s Method is a special case of the technique of using nested multiplication to evaluate a poly nomial more accurately and more efficiently We now brie y discuss this technique A polynomial pz is typically written in one of three forms 0 power form pz mm an1m 1 alm a0 0 shifted power form pm anm 7mg an1x7 x0 1 a1x7m0 010 This form is used in Taylor s Theorem If the center we is zero then this form reduces to the power form 0 Newton form This is the most general form in which PW a0 90 90019190 19195 a1 96 961P290 midis aim z 7 n71Pn pnx an If the centers m0 m1 mn1 are all equal then this form reduces to the shifted power form or the power form if they are all zero Given a number 2 the nested multiplication procedure applied to a polynomial pz in Newton form computes the numbers 0 b1 bn using a recurrence relation similar to that used in Horner s Method bnan bk akzizkbk1 kn71n72210 Then 192 0 Furthermore the numbers 0 b1 1 are the coef cients Ofpx in the Newton form with the modi ed centers 2 m0 m1 zn2 It follows that a polynomial can be represented in Newton form with arbitrary centers m0 m1 mnA simply by applying nested multiplication n times with z zi fori012n71 Mullerls Method An alternative approach to nding the roots of a polynomial pz is a generalization of the Secant Method known as Muller s Method As the Secant Method computes the next iterate zk by nding the root of the linear function that agrees with pz at the previous two iterates MA and zk Muller s Method computes n1 by nding the roots of the quadratic function that agrees with pz at the previous three iterates 2 MA and zk Since this quadratic function in general will have two distinct roots zk is chosen to be the root that is closest to m Just as the Secant Method requires two initial guesses mo and 1 Muller s Method requires three initial guesses 0 1 and 2 One advantage of Muller s Method over the approach of using de ation in conjunction with Newton s Method is it can nd complex roots even if the initial guesses are real whereas Newton s Method cannot We now describe in detail how Muller s Method works Given the initial iterates 0 1 and 2 we show how the next iterate mg is computed We need to nd a quadratic polynomial qz that passes through the points x0px0 zlpz1 and x2px2 where pz is the polynomial whose roots we wish to compute As we will learn in later lectures this quadratic polynomial is unique We write qz in the form 6190 190 902V 590 i 902 07 where the coef cients a b and c are to be determined This form is useful because we can nd the root of qz that is closest to mg by nding the root of azz bzz c that is of smallest magnitude By substituting 2 for z in qm we see that qz2 c so from the condition qz2 pm2 we obtain 0 pm2 It remains to compute a and b For convenience we let ho mo 7 m2 and In ml 7 m2 We also de ne 60 29960 MM 61 29961 29962 ho 7 hi It follows from the conditions qz0 pz0 and qz1 pz1 that a and b satisfy the system of equations 1713 5710 19902 19900 ahf bhl 19952 19901 which simpli es to aho b 60 ahl b 61 Subtracting the second equation from the rst yields the equation ah0 7 711 60 7 61 which in turn yields the solutions 60 7 61 a h0 hi 7 b607ah0 As discussed previously we need to compute the root of azz bx c 0 that is smallest in magnitude If we examine the quadratic formula 71 i V192 7 4m m 2a 7 the smallest root is obtained by choosing the plus sign if b gt 0 and the minus sign if b lt 0 However this causes a subtraction to be performed which could lead to catastrophic cancellation Therefore we use the alternative form of the quadratic formula 7 26 b i b2 7 4ac39 To obtain the smallest root we need to maximize the magnitude of the denominator so we choose the sign to match the sign of 1 Based on the form of qm we conclude that the next iterate 3 is given by 2 c 353 2 7 b sgnbxb2 7 4ac where sgn denotes the signum function that indicates the sign of a number It is de ned by 1 ifmgt0 sgnz 71 ifz lt 0 0 ifm0 Having computed m3 we can continue this process computing the next iterate 4 by constructing the quadratic polynomial qz that passes through the points m1pm1 zgpz2 and zgpz3 and then nding the root of qz that is closest to 33 If there is the possibility of complex roots then we must instead compute the smallest root of azz bx c by determining which sign causes the denominator to have the largest modulus where the modulus of the complex number 2 a bi denoted by lzl is given by 2 Vaz b2

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.