Trapesform - Trapezoidal rule

Funktionen f ( x ) (i blått) approximeras av en linjär funktion (i rött).

I matematik , och närmare bestämt i numerisk analys , är den trapetsformade regeln (även känd som trapetsregeln eller trapetsregeln - se Trapezoid för mer information om terminologi) en teknik för att närma sig den bestämda integralen .

${\ displaystyle \ int _ {a}^{b} f (x) \, dx.}$

Trapesregeln fungerar genom att approximera regionen under grafen över funktionen som en trapetsform och beräkna dess yta. Det följer att ${\ displaystyle f (x)}$

${\ displaystyle \ int _ {a}^{b} f (x) \, dx \ approx (ba) \ cdot {\ tfrac {1} {2}} (f (a)+f (b)).}$

Den trapetsformade regeln kan ses som ett resultat som erhålls genom att medelvärdet av vänster och höger Riemann -summa , och definieras ibland på detta sätt. Integralen kan ännu bättre approximeras genom att partitionera integrationsintervallet , tillämpa trapetsregeln på varje delintervall och summera resultaten. I praktiken är denna "kedjade" (eller "sammansatta") trapetsformiga regel vanligtvis vad som menas med "integrering med trapetsformen". Låt vara en partition av sådant och vara längden på den -e delintervallen (det vill säga ), då ${\ displaystyle \ {x_ {k} \}}$${\ displaystyle [a, b]}$${\ displaystyle a = x_ {0} <x_ {1} <\ cdots <x_ {N-1} <x_ {N} = b}$${\ displaystyle \ Delta x_ {k}}$${\ displaystyle k}$${\ displaystyle \ Delta x_ {k} = x_ {k} -x_ {k-1}}$

${\ displaystyle \ int _ {a}^{b} f (x) \, dx \ approx \ sum _ {k = 1}^{N} {\ frac {f (x_ {k-1})+f ( x_ {k})} {2}} \ Delta x_ {k} = {\ tfrac {\ Delta x} {2}} \ vänster (f (x_ {0})+2f (x_ {1})+2f ( x_ {2})+2f (x_ {3})+2f (x_ {4})+\ cdots+2f (x_ {N-1})+f (x_ {N}) \ höger).}$

En animering som visar vad den trapetsformade regeln är och hur felet i approximation minskar när stegstorleken minskar

Illustration av "kedjad trapetsformad regel" som används på en oregelbundet mellanrum av .${\ displaystyle [a, b]}$

Approximationen blir mer exakt som upplösning av skilje ökar (det vill säga, för större , minskar). När partitionen har ett regelbundet avstånd, som ofta är fallet, kan formeln förenklas för beräkningseffektivitet. ${\ displaystyle N}$${\ displaystyle \ Delta x_ {k}}$

Som diskuteras nedan är det också möjligt att sätta felgränser för noggrannheten av värdet av en bestämd integral uppskattad med hjälp av en trapetsformad regel.

Historia

Ett papper från 2016 rapporterar att trapetsregeln användes i Babylon före 50 fvt för att integrera Jupiters hastighet längs ekliptiken .

Numeriskt genomförande

Ojämnt rutnät

När avståndet mellan rutnätet är ojämnt kan man använda formeln

${\ displaystyle \ int _ {a}^{b} f (x) \, dx \ approx \ sum _ {k = 1}^{N} {\ frac {f (x_ {k-1})+f ( x_ {k})} {2}} \ Delta x_ {k}}$

Enhetligt rutnät

För en domän som diskretiseras i paneler med lika stora mellanrum kan avsevärd förenkling inträffa. Låta ${\ displaystyle N}$

${\ displaystyle \ Delta x_ {k} = \ Delta x = {\ frac {ba} {N}}}$

approximationen till integralen blir

${\ displaystyle {\ begin {align} \ int _ {a}^{b} f (x) \, dx & \ approx {\ frac {\ Delta x} {2}} \ sum _ {k = 1}^{ N} \ vänster (f (x_ {k-1})+f (x_ {k}) \ höger) \\ [6pt] & = {\ frac {\ Delta x} {2}} (f (x_ {0 })+2f (x_ {1})+2f (x_ {2})+2f (x_ {3})+\ dotsb+2f ​​(x_ {N-1})+f (x_ {N})) \\ [6pt] & = {\ frac {\ Delta x} {2}} \ vänster (f (x_ {0})+f (x_ {N})+2 \ sum _ {k = 1}^{N-1 } f (x_ {k}) \ höger) \\ [6pt] & = \ Delta x \ vänster (\ sum _ {k = 1}^{N-1} f (x_ {k})+{\ frac { f (x_ {N})+f (x_ {0})} {2}} \ höger) \ slut {anpassad}}}$

vilket kräver färre utvärderingar av funktionen för att beräkna.

Felanalys

En animation som visar hur approximationen av trapetsformen förbättras med fler remsor för ett intervall med och . I takt med att antalet intervaller ökar, så ökar också resultatets noggrannhet.${\ displaystyle a = 2}$${\ displaystyle b = 8}$${\ displaystyle N}$

Felet i den sammansatta trapetsformade regeln är skillnaden mellan värdet på integralen och det numeriska resultatet:

${\ displaystyle {\ text {error}} = \ int _ {a}^{b} f (x) \, dx-{\ frac {ba} {N}} \ vänster [{f (a)+f ( b) \ över 2}+\ sum _ {k = 1}^{N-1} f \ vänster (a+k {\ frac {ba} {N}} \ höger) \ höger]}$

Det finns ett tal ξ mellan a och b , så att

${\ displaystyle {\ text {error}} =-{\ frac {(ba)^{3}} {12N^{2}}} f '' (\ xi)}$

Det följer att om integranden är konkav (och därmed har ett positivt andra derivat), är felet negativt och den trapetsformade regeln överskattar det verkliga värdet. Detta kan också ses från den geometriska bilden: trapezoiderna omfattar hela området under kurvan och sträcker sig över det. På samma sätt ger en konkav-ned- funktion en underskattning eftersom området inte är redovisat under kurvan, men ingen räknas ovan. Om intervallet för integralen som approximeras inkluderar en böjningspunkt är felet svårare att identifiera.

En asymptotisk feluppskattning för N → ∞ ges av

${\ displaystyle {\ text {error}} =-{\ frac {(ba)^{2}} {12N^{2}}} {\ big [} f '(b) -f' (a) {\ stor]}+O (N^{-3}).}$

Ytterligare termer i denna feluppskattning ges av summeringsformeln Euler – Maclaurin.

Flera tekniker kan användas för att analysera felet, inklusive:

1. Fourier-serier
2. Restberäkning
3. Euler – Maclaurin summeringsformel
4. Polynomisk interpolation

Det hävdas att konvergenshastigheten för den trapetsformade regeln återspeglar och kan användas som en definition av klasserna av funktionernas jämnhet.

Bevis

Antag först att och . Låta vara funktionen så att är felet av trapetsregeln på en av intervaller . Sedan ${\ displaystyle h = {\ frac {ba} {N}}}$${\ displaystyle a_ {k} = a+(k-1) h}$${\ displaystyle g_ {k} (t) = {\ frac {1} {2}} t [f (a_ {k})+f (a_ {k}+t)]-\ int _ {a_ {k} }^{a_ {k}+t} f (x) dx}$${\ displaystyle | g_ {k} (h) |}$${\ displaystyle [a_ {k}, a_ {k}+h]}$

$${\ displaystyle {dg_ {k} \ över dt} = {1 \ över 2} [f (a_ {k})+f (a_ {k}+t)]+{1 \ över 2} t \ cdot f ' (a_ {k}+t) -f (a_ {k}+t),}$$

och

$${\ displaystyle {d^{2} g_ {k} \ över dt^{2}} = {1 \ över 2} t \ cdot f '' (a_ {k}+t).}$$

Antag nu att det som håller om är tillräckligt smidigt. Det följer sedan det ${\ displaystyle \ left \ vert f '' (x) \ right \ vert \ leq f '' (\ xi),}$${\ displaystyle f}$

$${\ displaystyle \ left \ vert f '' (a_ {k}+t) \ right \ vert \ leq f '' (\ xi)}$$

vilket motsvarar , eller${\ displaystyle -f '' (\ xi) \ leq f '' (a_ {k}+t) \ leq f '' (\ xi)}$${\ displaystyle -{\ frac {f '' (\ xi) t} {2}} \ leq g_ {k} '' (t) \ leq {\ frac {f '' (\ xi) t} {2} }.}$

Sedan och , ${\ displaystyle g_ {k} '(0) = 0}$${\ displaystyle g_ {k} (0) = 0}$

$${\ displaystyle \ int _ {0}^{t} g_ {k} '' (x) dx = g_ {k} '(t)}$$

$${\ displaystyle \ int _ {0}^{t} g_ {k} '(x) dx = g_ {k} (t).}$$

Med hjälp av dessa resultat hittar vi

$${\ displaystyle -{\ frac {f '' (\ xi) t^{2}} {4}} \ leq g_ {k} '(t) \ leq {\ frac {f' '(\ xi) t^ {2}} {4}}}$$

och

$${\ displaystyle -{\ frac {f '' (\ xi) t^{3}} {12}} \ leq g_ {k} (t) \ leq {\ frac {f '' (\ xi) t^{ 3}} {12}}}$$

Låt oss hitta ${\ displaystyle t = h}$

$${\ displaystyle -{\ frac {f '' (\ xi) h^{3}} {12}} \ leq g_ {k} (h) \ leq {\ frac {f '' (\ xi) h^{ 3}} {12}}.}$$

Sammanfattar alla lokala feltermer vi hittar

$${\ displaystyle \ sum _ {k = 1}^{N} g_ {k} (h) = {\ frac {ba} {N}} \ vänster [{f (a)+f (b) \ över 2} +\ sum _ {k = 1}^{N-1} f \ vänster (a+k {\ frac {ba} {N}} \ höger) \ höger]-\ int _ {a}^{b} f (x) dx.}$$

Men vi har också

$${\ displaystyle -\ sum _ {k = 1}^{N} {\ frac {f '' (\ xi) h^{3}} {12}} \ leq \ sum _ {k = 1}^{N } g_ {k} (h) \ leq \ sum _ {k = 1}^{N} {\ frac {f '' (\ xi) h^{3}} {12}}}$$

och

$${\ displaystyle \ sum _ {k = 1}^{N} {\ frac {f '' (\ xi) h^{3}} {12}} = {\ frac {f '' (\ xi) h^ {3} N} {12}},}$$

så att

$${\ displaystyle -{\ frac {f '' (\ xi) h^{3} N} {12}} \ leq {\ frac {ba} {N}} \ vänster [{f (a)+f (b ) \ över 2}+\ sum _ {k = 1}^{N-1} f \ vänster (a+k {\ frac {ba} {N}} \ höger) \ höger]-\ int _ {a} ^{b} f (x) dx \ leq {\ frac {f '' (\ xi) h^{3} N} {12}}.}$$

Därför är det totala felet begränsat av

$${\ displaystyle {\ text {error}} = \ int _ {a}^{b} f (x) dx-{\ frac {ba} {N}} \ vänster [{f (a)+f (b) \ över 2}+\ sum _ {k = 1}^{N-1} f \ vänster (a+k {\ frac {ba} {N}} \ höger) \ höger] = {\ frac {f '' (\ xi) h^{3} N} {12}} = {\ frac {f '' (\ xi) (ba)^{3}} {12N^{2}}}.}$$

Periodiska funktioner och toppfunktioner

Trapesregeln konvergerar snabbt för periodiska funktioner. Detta är ett enkelt följd av Euler-Maclaurin summerat formel , som säger att om är gånger kontinuerligt deriverbar med perioden${\ displaystyle f}$${\ displaystyle p}$${\ displaystyle T}$

${\ displaystyle \ sum _ {k = 0}^{N-1} f (kh) h = \ int _ {0}^{T} f (x) \, dx+\ sum _ {k = 1}^{ \ lfloor p/2 \ rfloor} {\ frac {B_ {2k}} {(2k)!}} (f^{(2k-1)} (T) -f^{(2k-1)} (0) )-(-1)^{p} h^{p} \ int _ {0}^{T} {\ tilde {B}} _ {p} (x/T) f^{(p)} (x ) \, \ mathrm {d} x}$

var och är den periodiska förlängningen av th Bernoulli -polynomet. På grund av periodiciteten avbryts derivaten vid slutpunkten och vi ser att felet är . ${\ displaystyle h: = T/N}$${\ displaystyle {\ tilde {B}} _ {p}}$${\ displaystyle p}$${\ displaystyle O (h^{p})}$

En liknande effekt är tillgänglig för toppliknande funktioner, såsom Gaussian , Exponentially modifierad Gaussian och andra funktioner med derivat vid integrationsgränser som kan försummas. Utvärderingen av hela integralen av en gaussisk funktion med trapetsform med 1% noggrannhet kan göras med bara 4 poäng. Simpsons regel kräver 1,8 gånger fler poäng för att uppnå samma noggrannhet.

Även om en del ansträngningar har gjorts för att utvidga Euler-Maclaurin-summeringsformeln till högre dimensioner, är det mest okomplicerade beviset på den snabba konvergensen av den trapetsformade regeln i högre dimensioner att reducera problemet till konvergensen i Fourierserier. Detta resonemang visar att om det är periodiskt i ett -dimensionellt utrymme med kontinuerliga derivat är konvergenshastigheten . För mycket stora dimensioner visar att Monte-Carlo-integration sannolikt är ett bättre val, men för 2 och 3 dimensioner är samplingsprovtagning effektiv. Detta utnyttjas i beräkning av fast tillståndsfysik där samplad provtagning över primitiva celler i det ömsesidiga gallret kallas Monkhorst-Pack-integration . ${\ displaystyle f}$${\ displaystyle n}$${\ displaystyle p}$${\ displaystyle O (h^{p/d})}$

"Grova" funktioner

För funktioner som inte finns i C ² är felbegränsningen ovan inte tillämplig. Fortfarande kan felgränser för sådana grova funktioner härledas, vilket vanligtvis visar en långsammare konvergens med antalet funktionsutvärderingar än beteendet som anges ovan. Intressant nog har trapesregeln i detta fall ofta skarpare gränser än Simpsons regel för samma antal funktionsutvärderingar. ${\ displaystyle N}$${\ displaystyle O (N^{-2})}$

Tillämplighet och alternativ

Trapesregeln är en i en familj av formler för numerisk integration som kallas Newton – Cotes -formler , varav mittpunktsregeln liknar trapetsregeln. Simpsons regel är en annan medlem av samma familj och har i allmänhet snabbare konvergens än trapetsformen för funktioner som är två gånger kontinuerligt differentierbara, men inte i alla specifika fall. För olika klasser av tuffare funktioner (sådana med svagare jämnhetsförhållanden) har den trapetsformade regeln emellertid snabbare konvergens än Simpsons regel.

Dessutom tenderar den trapetsformade regeln att bli extremt exakt när periodiska funktioner är integrerade under sina perioder, vilket kan analyseras på olika sätt . En liknande effekt är tillgänglig för toppfunktioner.

För icke-periodiska funktioner är dock metoder med ojämnt fördelade punkter som Gauss-kvadratur och Clenshaw-Curtis-kvadratur i allmänhet mycket mer exakta; Clenshaw – Curtis -kvadratur kan ses som en förändring av variabler för att uttrycka godtyckliga integraler när det gäller periodiska integraler, vid vilken punkt den trapetsformade regeln kan tillämpas exakt.

Se även

• Gaussisk kvadratur
• Newton – Cotes formler
• Rektangelmetod
• Rombergs metod
• Simpsons regel
• Volterra integral ekvation#Numerisk lösning med hjälp av trapetsform

Anteckningar

Referenser

externa länkar

• Trapezformel. IP Mysovskikh , Encyclopedia of Mathematics , red. M. Hazewinkel
• Anteckningar om konvergensen av trapetsformad regelkvadratur
• En implementering av trapetsformad kvadratur från Boost.Math