Heun's method: Difference between revisions

Revision as of 17:17, 4 August 2012

Latest revision as of 09:07, 29 April 2024

(35 intermediate revisions by 33 users not shown)

Line 1:

{{Short description|Procedure for solving ODEs}}

In [[mathematics]] and [[computational science]], '''Heun's method''' may refer to the '''improved'''<ref>{{Citation | last1=Süli | first1=Endre | last2=Mayers | first2=David | title=An Introduction to Numerical Analysis | publisher=[[Cambridge University Press]] | isbn=0-521-00794-1 | year=2003}}.</ref> or '''modified Euler's method''' (that is, the '''explicit trapezoidal rule'''<ref>

{{Citation | last1=Ascher | first1=Uri M. | last2=Petzold | first2=Linda R.|author2-link=Linda Petzold | title=Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations | publisher=[[Society for Industrial and Applied Mathematics]] | ___location=Philadelphia | isbn=978-0-89871-412-8 | year=1998}}.</ref>), or a similar two-stage [[Runge–Kutta method]]. It is named after [[Karl L. W. M. Heun]] and is a [[numerical analysis|numerical]] procedure for solving [[Ordinary_differential_equation|ordinary differential equationsequation]]s (ODEs) with a given [[Initial_value_problemInitial value problem|initial value]]. Both variants can be seen as extensions of the [[Euler method]] into two-stage second-order Runge–Kutta methods.

The procedure for calculating the numerical solution to the initial value problem via the improved Euler's method is:

:<math>y'(t) = f(t,y(t)), \qquad \qquad y(t_0)=y_0, </math>

by way of Heun's method, is to first calculate the intermediate value <math>\tilde{y}_{i+1}</math> and then the final approximation <math>y_{i+1}</math> at the next integration point.

:<math>\tilde{y}_{i+1} = y_i + h f(t_i,y_i)</math>

:<math>y_{i+1} = y_i + \frac{h}{2}([f(t_i, y_i) + f(t_{i+1},\tilde{y}_{i+1})).],</math>

:

where <math>h</math> is the step size and <math>t_{i+1}=t_i+h</math>.

==Description==

Euler’sEuler's method is used as the foundation for Heun’sHeun's method. Where Euler’sEuler's method uses the line tangent line to the actualfunction solutionat the beginning of the curveinterval as an estimate of the curveslope itself, providedof the stepfunction sizeover remainsthe small enoughinterval, contendsassuming that if the twostep willsize notis driftsmall, toothe farerror apartwill be small. In realityHowever, even when extremely small step sizes are used, over a large number of steps the error starts to accumulate and boththe estimate diverges from the actual solutionsfunctional divergevalue.

Where the solution curve is concave up, its tangent line will underestimate the vertical coordinate of the next point and vice versa for a concave down solution. The ideal prediction line would hit the curve at its next predicted point. In reality, there is no way to know whether the solution is concave-up or concave-down, and hence if the next predicted point will overestimate or underestimate its vertical value. The concavity of the curve cannot be guaranteed to remain consistent either and the prediction may overestimate and underestimate at different points in the ___domain of the solution.

Heun’sHeun's Method addresses this problem by considering the interval spanned by the tangent line segment as a whole. Taking a concave-up example, the left tangent prediction line underestimates the slope of the curve for the entire width of the interval from the current point to the next predicted point. If the tangent line at the right end point is considered (which can be estimated using Euler’sEuler's Method), it has the opposite problem.<ref>{{cite web

<ref>{{cite web

|title=Numerical Methods for Solving Differential Equations

|publisher=San Joaquin Delta College

|url=http://calculuslab.deltacollege.edu/ODE/7-C-2/7-C-2-h.html

|archiveurl=httphttps://web.archive.org/web/20090212005921/http://calculuslab.deltacollege.edu/ODE/7-C-2/7-C-2-h.html

|archivedate=2009-02-12}}</ref>

The points along the tangent line of the left end point have vertical coordinates which all underestimate those that lie on the solution curve, including the right end point of the interval under consideration. The solution is to make the slope greater by some amount. Heun’sHeun's Method considers the tangent lines to the solution curve at ''both'' ends of the interval, one which ''overestimates'', and one which ''underestimates'' the ideal vertical coordinates. A prediction line must be constructed based on the right end point tangent’stangent's slope alone, approximated using Euler's Method. If this slope is passed through the left end point of the interval, the result is evidently too steep to be used as an ideal prediction line and overestimates the ideal point. Therefore, the ideal point lies approximately half wayhalfway between the erroneous overestimation and underestimation, the average of the two slopes.

[[File:Heun's Method Diagram.jpg|thumb|right|alt=Heun's Method.|A diagram depicting the use of Heun's method to find a less erroneous prediction when compared to the lower order Euler's Method]]

Euler’sEuler's Method is used to roughly estimate the coordinates of the next point in the solution, and with this knowledge, the original estimate is re-predicted or ''corrected'' .<ref>

{{Citation | last1=Chen

| first1=Wenfang.

Line 31 ⟶ 33:

| ___location=MA, USA

| isbn=981-238-292-5

| year=2003}}.</ref>. Assuming that the quantity <math>\textstyle f(x, y)</math> on the right hand side of the equation can be thought of as the slope of the solution sought at any point <math>\textstyle (x, y) </math>, this can be combined with the Euler estimate of the next point to give the slope of the tangent line at the right end-point. Next the average of both slopes is used to find the corrected coordinates of the right end interval.

==Derivation==

:<math>\textstyle Slope_text{Slope}_{\text{left}} = f(x_i, y_i)</math>

:<math>\textstyle Slope_text{Slope}_{\text{right}} = f(x_i + h, y_i + h f(x_i, y_i))</math>

:<math>\textstyle Slope_text{Slope}_{\text{ideal}} = (\frac{1/}{2)} (Slope_\text{Slope}_{\text{left}} + Slope_\text{Slope}_{\text{right}})</math>

Using the principle that the slope of a line equates to the rise/run, the coordinates at the end of the interval can be found using the following formula:

:<math>\textstyle Slope_text{Slope}_{\text{ideal}} = (\frac{\Delta y /}{h)} </math>

:<math>\textstyle \Delta y = h (Slope_\text{Slope}_{\text{ideal}})</math>

:<math>\textstyle x_{i+1} = x_i + h</math>, <math>\textstyle y_{ni+1} = y_i + \Delta y</math>

:<math>\textstyle y_{i+1} = y_i + h Slope_\text{Slope}_{\text{ideal}}</math>

:<math>y_{i+1} = y_{i} + \frac{1}{2} h (Slope_\text{Slope}_{\text{left}} + Slope_\text{Slope}_{\text{right}})</math>

:<math>y_{i+1} = y_{i} + \frac{h}{2}(f(x_i, y_i) + f(x_i + h, y_i + hf(x_i, y_i)))</math>

The accuracy of the Euler method improves only linearly with the step size is decreased, whereas the Heun Method improves accuracy quadratically

.<ref>{{cite web|url=http://livetoad.org/Courses/Documents/214a/Notes/euler-heun_method.pdf|title=The Euler-Heun Method|last=|first=|date=|website=|publisher=LiveToad.org|url-status=dead|archive-url=https://web.archive.org/web/20181014204120/http://livetoad.org/Courses/Documents/214a/Notes/euler-heun_method.pdf|archive-date=2018-10-14|access-date=}}</ref>. The scheme can be compared with the [[Explicit and implicit methods|implicit]] [[trapezoidal method]], but with <math>f(t_{i+1},y_{i+1})</math> replaced by <math>f(t_{i+1},\tilde{y}_{i+1})</math> in order to make it explicit. <math>\tilde{y}_{i+1}</math> is the result of one step of [[Euler's method]] on the same initial value problem. So, Heun's method is a [[predictor-corrector method]] with forward [[Euler's method]] as predictor and [[trapezoidal method]] as corrector.

<ref>{{cite web

|title=The Euler-Heun Method

|publisher=LiveToad.org

|url=http://livetoad.org/Courses/Documents/214a/Notes/euler-heun_method.pdf

}}</ref>. The scheme can be compared with the [[Explicit and implicit methods|implicit]] [[trapezoidal method]], but with <math>f(t_{i+1},y_{i+1})</math> replaced by <math>f(t_{i+1},\tilde{y}_{i+1})</math> in order to make it explicit. <math>\tilde{y}_{i+1}</math> is the result of one step of [[Euler's method]] on the same initial value problem. So, Heun's method is a [[predictor-corrector method]] with forward [[Euler's method]] as predictor and [[trapezoidal method]] as corrector.

==Runge–Kutta method==

Line 69 ⟶ 67:

|}

The other method referred to as Heun's method (also known as Ralston's method) has the Butcher tabletableau:<ref>

{{Citation | last1=Leader | first1=Jeffery J.| title=Numerical Analysis and Scientific Computation | publisher=[[Addison-Wesley]] | ___location=Boston | isbn=0-201-73499-0 | year=2004}}.</ref>:

{| cellpadding=3px cellspacing=0px

Line 80 ⟶ 78:

||| style="border-right:1px solid;" | || 1/4 || 3/4

|}

This method minimizes the truncation error.

==References==

{{commons category|Heun's method}}

<references/>

{{Numerical integrators}}

Line 89:

[[Category:Numerical differential equations]]

[[Category:Runge–Kutta methods]]

[[de:Heun-Verfahren]]

[[sv:Heuns metod]]