This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.
A linear equation is an algebraic equation in which the output is directly proportional to the input, which makes it easy to plot on a graph. It follows the superposition principle, as well as the linearity principle and can easily be solved by the substitution method. Whereas a nonlinear equation is one in which the terms of the equation have a variable with degree two or higher than two. And hence, a system of nonlinear equations is defined as a system which contains at least one nonlinear equation.
NONLINEAR equations are difficult to solve and give rise to interesting phenomena such as chaos. Nonlinear problems are of concern to engineers, physicists and mathematicians because most physical systems are inherently nonlinear in nature.
SYSTEMS of nonlinear equations occur in many domains of practical importance such as engineering, mechanics, medicine, chemistry, and robotics. Most equations, if not directly solvable, are usually solved using qualitative or numerical analysis. Hence, finding solutions for them have become an important aspect of numerical analysis. The problem is nondeterministic, polynomial-time hard, and has a very high computational complexity due to several numerical issues. The weather, for example, is famously chaotic, where small changes in one part of the system result in complex effects throughout.
Higher order polynomials and functions involving trigonometric functions or other transcendental functions can be difficult to solve in an explicit, analytical form. There are many numerical methods available to solve equations such as these. A few of the important, common techniques are bisection, Newton's method, and iteration.
ROOTS of a nonlinear equation f(x) are the values of x which give the value of the equation. Hence, they are alternatively known as zeros of the equation.
2. Solving a System of Non-Linear Equations:
Solving such a system involves finding all the possible solutions of the polynomial equations contained in the mentioned system. And generally the only method feasible is iterative methods.
There are a number of iterative methods that have been tried and used successfully in various problem situations. These methods, generally, attempt to solve the problem by performing successive approximations which are expected to give the true solution.
Iterative methods are classified into two based on the number of guesses used:
Open End methods
Bracketing methods, also known as interpolation methods, start with two initial approximates to the root that 'bracket' the root and then reduce the bracket till the solution has been reached.
False position method
Open end methods, also known as extrapolation methods, generally use a single (or two) start value that does not necessarily bracket the root.
The following methods fall under this category:
For the following project, four methods have been highlighted explaining their algorithm, drawbacks and major applications in technical fields.
Starting the process:
Before an iterative process is initiated, an approximate value of the root or an interval that contains the root is to be determined.
One simple method of guessing the root/interval of the function f(x) is graphical representation of the said function which not only provides us with a rough estimate of the root, but can also help us in understanding the properties of the function, thereby identifying possible problems in numerical computing.
An iterative process must be terminated at some stage. We must have an objective to work towards to decide the criterion for deciding when to stop the process.
In common practice, iterative methods are stopped when two successive estimates are the same. However in computing, as the number of significant digits is higher this would take a much longer time. And if an error occurs the number of iterations could be infinite. Hence a limit should be put to the number of iterations, in addition to the earlier condition.
We have the problem of finding the real roots of a single equation f(x)=0, which is the same as finding zeros of a real valued function. Hence, the terms roots and zeros are used interchangeably
The simplest way of finding the roots of the equation would be to plot the function f(x) against x and the point at which it crosses the x-axis is taken as the zero or root of the equation. This is indeed, a crude but reliable method for solving non-linear equations. For better accuracy, we plot it on a larger scale.
However large a scale we plot it on though, the roots will not be precise. Hence the need for bisection method is all the more obvious. Once the root has been located in a given interval, we can conveniently locate the root using bisection method.
Fig 2. Graphical representation of the equation f(x) = cosx - x3 + 1
2.1 The Bisection Method:
The Bisection Method (also known as Interval Halving Method) is a simple and robust method, but it can also be painstakingly slow at times. This method generates a sequence of nested intervals where each interval is guaranteed to contain at least one root of the equation.
It is a type of incremental search method where the interval is always reduced by half. If a function changes sign over the interval, the function's value at its mid-point is evaluated. The location of the root is then determined as lying at the mid-point of the sub-interval within which the sign change occurs. This process is repeated till the desired accuracy is achieved. In ten repetitions, the original interval reduces by a factor of 210 = 1024!
The method involves five simple steps:
STEP 1: Let f(x) = 0.
STEP 2: Choose two values xl and xu such that f(xl) . f(xu) < 0. This is done to ensure that a root lies between xl and xu.
STEP 3: Compute xm = (xl + xu) / 2.
STEP 4: Find f(xl) . f(xu).
Three cases arise:
f(xl) . f(xm) < 0, then
xl = xl
and xu = xm
f(xl) . f(xm) > 0, then
xl = xm
and xu = xu
f(xl) . f(xm) = 0, then
root = xm
STEP 5: Go back to STEP 3 and repeat the process till we get desired result.
[Type a quote from the document or the summary of an interesting point. You can position the text box anywhere in the document. Use the Text Box Tools tab to change the formatting of the pull quote text box.]Flow-chart
[Type a quote from the document or the summary of an interesting point. You can position the text box anywhere in the document. Use the Text Box Tools tab to change the formatting of the pull quote text box.]
2.1.3 Error Analysis:
Suppose we have an initial boundary on the problem [a , b], then the maximum error of using either a or b for our approximation is h = b âˆ’ a. Since we halve the width of the interval in each iteration, the error is reduced by a factor of 2, and so the error after n iterations will be h/2n.
Therefore, we can find out how many steps are required. If error at every step (Îµstep) is fixed, then we can directly know how many steps are required, after which we are assured that the absolute error is less than Îµstep. The following inequality is used to find the error:
n = [log2(h/ Îµstep)]
For example, suppose that our initial interval is [0.7, 1.5]. If we have an Îµstep value of 1-5, then we require a minimum of âŒˆlog2( 0.8/1-5 )âŒ‰ = 17 steps.
Considering this method, it may happen at some stage that the mid-point of the interval falls within the domain of indeterminacy associated with the zero. To explain such a situation, Wilkinson(1988) defines the domain of indeterminacy associated with every zero of the given function, within which the computed value of the function is totally governed by the roundoff error. In such a case, the value of the function at that point and hence its sign is totally governed by the roundoff error and the process of bisection might locate the root in the wrong subinterval. Hence while computing, it is always best to have an upper limit on the number of iterations rather than testing for any other criteria which may lead to a non-terminating loop.
Bisection method can be used for shot detection in video content for the Digital Video Library (DVL). DVL is a networked Internet application allowing for storage, searching, cataloguing, browsing, retrieval, searching and uni-casting video sequences. The browsing functionality can be significantly facilitated by a fast shot detection process. Experiments show that usage of the bisection method, allows for accelerating shot detection about 3÷150 times (related to the shot density). Two important assumptions are to be made in order to use this method though. First, it is necessary to tell if every two randomly picked video frames of a video sequence that is to be segmented, belong to the same shot. Secondly, there should not be two or more shots having the same feature within the video sequence. There are two possible networked applications mentioned: a medical DVL developed for learning purposes and a hypothetical networked news application.
Bisection Method can be used for changing classification threshold value for a more cost sensitive neural network learning. The threshold varying bisection method is much better than the traditional fixed-threshold method based neural network. However, when compared to probabilistic neural network, the method works well only when the misclassification cost asymmetries are low.
Even in simple day-to-day applications, bisection method can be very useful. For an example, if you are browsing the history log of a code sheet and want to know when a particular line was added and who did it, this method can be very useful.
First, you could open the middle of the whole set and if the line is already there, you know you are now limited to the lower half of the set. This method is way more effective than opening each entry on the database one by one.
2.2 The Regula-Falsi Method:
We know that Bisection is a perfectly legal technique for determining roots; however, its "brute-force" approach is relatively inefficient. False Position, or Regula-Falsi method, is a technique based on a graphical insight.
One negative notion towards the bisection method is that, while dividing the interval from xi-1 to xi into equal halves, no account is taken of the magnitudes of f(xi-1) and f(xi). For example, if f(xi-1) is much closer to zero than f(xi), it is possible that the root is closer to xi-1 than to xi. Hence, the difference between bisection and regula-falsi is that in the latter the new estimate is arrived at by linear interpolation while in the other it is the midpoint, regardless of the value of the functions.
When the line intersects with the x-axis after linear interpolation, we get an improved estimate of the root. The fact that the replacement of the curve by a straight line gives a "false position" of the root is the origin of the name, "Method of False Position", or as known in Latin, "Regula Falsi". This method is also called as the linear interpolation method.
To solve questions related to this method, the steps required to be followed are:
STEP 1: Check xi-1 and xi such that f(xi-1) . f(xi) < 0.
STEP 2: Compute, xi+1 = xi - [f(xi) . (xi - xi-1) / f(xi) - f(xi-1)]
STEP 3: First find, f(xi+1) . f(xi-1). If f(xi+1) . f(xi-1) < 0, then xi = xi+1 otherwise xi-1 = xi+1.
STEP 4: Go to STEP 2 and repeat the above process until two successive iterations are equal to the given n-significant digits.
Fig 2.2 Flow-chart for Regula-Falsi Method
2.2.3 Error Analysis:
The error analysis for this method is complicated when compared to the bisection method. However, if one end point is made to be fixed, it can be proved that this is still an O(h) operation, i.e. it is the same rate as the bisection method, usually faster, but possibly slower. For differentiable functions, the convergence is faster when the fixed point is closer to the actual root.
The regula falsi method is a good method for when information on the location of the zeros of the equation is poor. And even though it is guaranteed to converge, the process may be very slow. The iterative process continues until it is stopped. Hence, this method is not very useful. This method can be improved to give a modified regula falsi method.
J. B. Phillips, A. S. Menawat and S. R. Carden in their article, "Modification of the Regula-Falsi method" have discussed how the method can be used to accelerate system convergence in the prediction of trace quantities of atmospheric pollutants.
Since equilibrium quantities of uncombusted fuel are quite small, due to the exothermic nature of combustion reactions, calculating the maximum theoretical efficiency that could be obtained in a combustion process is hard since the equations which describe the equilibrium state are long.
After reduction of the system to just one equation and one unknown, the Regula Falsi method can be applied in a modified form. It is modified through the introduction of an under-interpolation factor, which speeds up the convergence of the procedure and hence the method is referred to as successive under interpolation (SUI).
2.3 The Secant Method:
The Secant Method is an approach to decipher the root of a scalar-valued function f(x) of a variable 'x' when no information about the derivative exists. It is very similar to the regula falsi method with the only difference being that the condition for the function f(x) to have opposite signs at the two points used to generate the next estimation is dropped. This method also requires lesser iterations as compared to the Bisection Method as well as the Regula Falsi Method.
In contrast to the other bracketing methods, this method does not bracket the root, even to start the iteration. Hence, it is obvious the approximation need not always converge. On the other hand, when it does converge, it does so faster. Thus, dropping the need for bracketing the root improves the rate of convergence at the risk of non-convergence in some cases. The name 'secant' method comes from the fact that at any stage the next estimate can be obtained by drawing a secant line through the two most recent points.
Solving equations by this method requires four steps:
STEP 1: Let f(x) = 0.
STEP 2: Let the initial given two values be xi-1 and xi.
STEP 3: Compute, xi+1 = xi - [f(xi) . (xi-1 - xi) / f(xi-1) - f(xi)].
STEP 4: Repeat the process till two successive values of f(xi-1) are the same.
Fig 2.3 Flow-chart for Secant Method
2.3.3 Error Analysis:
The error analysis for the secant method is more complicated than the Regula-Falsi method since both end points are continuously being changed and so the iterations will not fall into the O(h) trap of the Regula-Falsi method. It can be depicted that the rate of convergence at a simple root is better than linear, but imperfect when compared to the quadratic convergence of Newton's method. It is given by the golden-ratio:
Ø = [(1 +) / 2] â‰ˆ 1.61803398875
And so, we can also show that the rate of convergence is O(h1.618).
In the Secant Method, there will always be the risk of non-convergence which will cause a lot of problems. And while solving the computed iterates, there is no guaranteed error bound.
In the 13th World Conference on Earthquake Engineering held in Vancouver, Canada on 1-6 August, 2004, scientists discussed on the efficient application of the Secant Method for Capturing the Peak Response of Complex Multi-Story Bldgs. The Secant Method is an iterative method in which the peak displacement response of a structure or structural component is determined from linear dynamic analyses of a model whose stiffness is updated to reflect a computed degree of degradation that is consistent with the computed peak displacement. The main application of this method to huge and complex multi-story buildings is that it facilitates capturing higher mode and torsional response while greatly reducing the number of iterations required to achieve convergence.
2.4 The Newton Method:
This is the most widely used method to locate the root of non-linear equations. The method is quite simple and straightforward. The method states that if an initial guess xi is made at the root, then a tangent can be drawn from the point [xi , f(xi)]. Wherever the tangent crosses the x-axis, that specific point will depict an improved estimate of the root. This method is thus evolved on the basis of this geometrical interpretation.
Newton's method converges faster as compared to the Bisection and Regula Falsi Method. It is also known as Newton-Raphson Method.
The method involves three steps:
STEP 1: Choose an initial value of xi such that f(xi) â‰ 0 and f'(xi) â‰ 0.
STEP 2: Compute xi+1 = xi - [f(xi) / f'(xi)]
STEP 3: Repeat STEP 2 till two successive values of f(xi+1) are equal OR values of the function are sufficiently close to zero.
Newton's method can also be used for finding the complex roots of non-linear equations, all that is required is that the initial value must be assumed to be a complex value and the procedure remains the same.
Fig 2.4 Flow-chart for Newton's Method
2.4.3 Error Analysis:
In this method, the error at the nth step is very closely judged by the error found in the (n - 1)th step. In day-to-day experience, we do not actually know what the error is. But this tells us that Newton's method converges very quickly.
Even though Newton's Method is often adequate, there are times when the method fails to achieve a solution or does not converge quickly. The cases are:
The approximation we make is far from the root.
The second derivative is very large.
The derivative at xi is very close to zero.
Newton-Raphson Method finds its application in vibration analysis, as it consists entirely of transcendental equations, which is a mix of trigonometric and hyperbolic terms. An example is the calculation of natural frequencies of continuous structures, such as beams and plates.
Newton-Raphson also falls into the category of algorithms to perform fast division in digital designs. It starts with a close approximation to the final answer and produces twice as many digits on each iteration. We first find the reciprocal of D, and multiply D by N to find the final quotient Q.
The steps are:
Calculate an estimate for the reciprocal of the divisor (D):Â x0.
Compute successively more accurate estimates of the reciprocal (x1,â€¦..,xk)
Compute the quotient by multiplying the dividend by the reciprocal of the divisor:Â QÂ =Â Nxk.
In order to apply Newton's method to find the reciprocal ofÂ D, it is necessary to find a functionÂ f(x)Â which has a zero atÂ XÂ = 1 /Â D. The obvious such function isÂ f(X) =Â DXÂ âˆ’ 1, but the Newton-Raphson iteration for this is unhelpful since it cannot be computed without already knowing the reciprocal ofÂ D. A function which does work isÂ f(X) = 1 /Â XÂ âˆ’Â D, for which the Newton-Raphson iteration gives
which can be calculated fromÂ XiÂ using only multiplication and subtraction.
If the error is defined asÂ Â then
Apply a bit-shift to the divisorÂ DÂ to scale it so thatÂ 0.5 <Â DÂ < 1.Â The same bit-shift should be applied to the numeratorÂ NÂ so that the quotient does not change. Then one could use a linear approximation in the form
to initialize Newton-Raphson
The coding for the program created for the project on solving non-linear equations is attached in the next section. It was created using the C language, implementing the algorithms of the four different methods, using C-Free Pro Ver. 5.0.