Rundung von Lagrange-Polynomen mit vielen Knoten abrunden

10

Bei einer Menge von Punkten in möchte ich berechnen genau. ist das Lagrange-Polynom in Bezug auf die Punkte mit als Knoten, dh Da dies ein Polynom vom Grad , könnte ich jede alte Gaußsche Quadratur von ausreichendem Grad verwenden. Dies funktioniert gut, wenn nicht zu groß ist, führt jedoch zu Ergebnissen, die durch Rundungsfehler für großes fehlerhaft sind . [ - 1 , 1 ] 1 - 1 L i ( x ){xj}j=1n[1,1]L i x j x i L i ( x ) = j i x - x j

11Li(x)dx
Lixjxinnn
Li(x)=jixxjxixj.
nnn

Irgendeine Idee, wie man diese vermeidet?

Nico Schlömer
quelle
3
Dies hängt davon ab, wo sich befinden. Haben Sie jedoch überprüft, ob sich Ihre 's gut benehmen? Im schlimmsten Fall, wenn gleichmäßig verteilt ist, tritt das Runge-Phänomen ( oszillierend und groß) auf. In diesem Fall handelt es sich nicht wirklich um Rundungsfehler, die Probleme verursachen. L i x j L ixjLixjLi
Kirill
2
Nitpick: Das Teilen durch kleine Zahlen ist eine gut konditionierte Operation. Vielmehr ist die anschließende Subtraktion großer, nahezu gleicher Zahlen schlecht konditioniert und führt zu numerischer Instabilität.
Kirill
Es scheint, als würden Sie versuchen zu berechnen wobei die Vandermonde-Matrix von . Können Sie sagen, wie hoch die Bedingungsnummer von ist? (2,0,23,0,25,0,)V1VxjV
Kirill

Antworten:

5

Die Berechnung von für die Lagrange-Polynome die auf einem beliebigen Gitter kann von der durchgeführt werden folgende zwei Schritte:

11Lk(x)dx
Lkxk,k=0,,n

  1. Berechnen Sie die Clenshaw-Curtis-Quadraturgewichte auf dem Chebyshev-Extrema-Gitter für : wobei für , andernfalls und für oder , andernfalls . Siehe das Papier von Waldvogel (2006) für weitere Details.wkccykk=0,,n

    yk=cos(kπn)wkcc=ckn(1j=1n/2bj4j21cos(2πjkn))
    bk:=1k=n/2bk:=2ck:=1k=0k=nck:=2

  2. Transformiere die Gewichte über die Transformationsmatrix in das beliebige Gitter , um die gesuchten Gewichte , wobei wkccxk,k=0,,nMwk

    wk=jMkjwjcc
    Mjk = Lj(yk).

Im Prinzip ist dies nur eine Clenshaw-Curtis-Quadratur mit Funktionswerten auf dem beliebigen Gitter , die jedoch durch Basistransformation erhalten wird (für eine allgemeine Referenz zu Clenshaw-Curtis siehe z. B. das Trefethen-Papier).xk

Der Algorithmus scheint ziemlich stabil zu sein, insbesondere im Vergleich zum Vandermonde-Ansatz, wie er in der Antwort von @Kirill angegeben ist : Obwohl er denselben Vorstellungen folgt - generieren Sie die Quadraturgewichte auf bekannter Basis und transformieren Sie sie dann in das neue Gitter - dies hätte erwartet werden können, da die Transformation in Bezug auf die Vandermonde-Matrix normalerweise stark schlecht konditioniert ist.


Beispiel: Erzeugung von Legendre-Lobatto-Quadraturgewichten

Wir betrachten das Beispiel der Legendere-Lobatto-Quadraturregel und vergleichen die Genauigkeit mit dem monomialen Ansatz. Als Referenz verwenden wir die Quadraturgewichte die vom Golub-Welsch-Algorithmus für verschiedene und berechnen den kumulierten Fehler Hier ist das Ergebnis: Man stellt fest, dass die Clenshaw-Curtis-Quadraturgewichte über den betrachteten Bereich von Gitterpunkten perfekt stabil sind und die Legendre-Gewichte bis zur Maschinengenauigkeit ( reproduzieren ).wkLegn

ϵn=k=1n(wkwkLeg)2
Geben Sie hier die Bildbeschreibung einϵ1015


Beispiel: Erzeugung von Newton-Cotes-Quadraturformeln

Wir betrachten die Erzeugung der Newton-Cotes-Quadraturformel auf gleich beabstandeten Gittern. Wiederum erwartet man eine schlechte Konditionierung, da kurz gesagt für die Polynominterpolation Gitter mit gleichem Abstand baaad sind.

Im folgenden Bild habe ich die absolute Summe der Gewichte berechnet . i|wi|/NGeben Sie hier die Bildbeschreibung ein

Bis zu beispielsweise 50 Gitterpunkte stimmen die Ergebnisse des Monomial- und des Clenshaw-Curtis-Ansatzes überein. Danach wird Clenshaw-Curtis besser - für das, was es wert ist. Eine direkte Interpretation ist, dass das gleichmäßig verteilte Gitter alles für beispielsweise ruiniert . Bei etwa schlägt der Zustand der Vandermonde-Matrix jedoch zurück und führt zu einem noch schlechteren Ergebnis.n>10n=50


Beispiel: Guass-Patterson-Quadratur

Dieses Beispiel ist @ NicoSchlömer zu verdanken. Ich kannte diese Regeln bisher nicht, also habe ich die Abszissen aus dieser Implementierung genommen und sowohl den Vandermonde- als auch den transformierten Clenshaw-Curtis-Ansatz angewendet (wobei der Vandermonde-Ansatz wie oben den Björk-Pereyra-Algorithmus verwendet).

Wie im Kommentar vorgeschlagen, berechnete ich dann den Fehler der Integration einer konstanten Funktion durch mit dem folgendes Ergebnis:

ϵ=1n|2i=1nwi|,

Geben Sie hier die Bildbeschreibung ein Aus diesem Bild geht hervor, dass der transformierte Clenshaw-Curtis-Ansatz weitaus effizienter ist als der Vandermonde-Ansatz (zumindest in der Arithmetik mit endlicher Genauigkeit). Trotzdem bricht Clenshaw-Curtis ab Index 7 zusammen, daher sollten andere Methoden angewendet werden.

Davidhigh
quelle
Danke für die interessante Antwort. Ich habe ein bisschen damit herumgespielt, fand aber die Abrundung bedeutend. Zum Beispiel sollte die Summe von immer 2 sein. Das stimmt bis zu n <5, aber für n == 6 erhalte ich bereits 1.9999949955991916 mit und Fehler in der 7. signifikanten Dezimalstelle. wk
Nico Schlömer
Ich habe vergessen zu erwähnen, dass dies mit Gauss-Patterson-Punkten ist, github.com/nschloe/quadpy/blob/master/quadpy/line_segment/… .
Nico Schlömer
@ NicoSchlömer: ok, das ist interessant, denn abgesehen von der Arithmetik mit beliebiger Genauigkeit (die die Julia-Implementierung zu bieten scheint) ist es schwer zu begründen, wie der Vandermonde-Ansatz sowieso genauer sein sollte (da der Vandermonde zu den Paradebeispielen für a gehört schlecht konditionierte Matrix). Ich werde die Frage bearbeiten und die Gauß-Patterson-Quadratur betrachten.
Davidhigh
Vielen Dank, David, dass du dir das alles angesehen hast. Es ist in der Tat interessant! Ich denke, es wäre eine lohnende Ergänzung dieses Beitrags, einen Vergleich mit gewöhnlicher Gauß-Legendre-Quadratur des entsprechenden Grades aufzunehmen. Ich würde vermuten, dass es wie Ihr Clenshaw-Curtis-Ansatz funktioniert. Außerdem ist es für jeden, der sich in Zukunft damit befasst, hilfreich, den Code auf Github oder so zu setzen und von hier aus zu verknüpfen. Wenn Sie die Antwort mit der höchsten Bewertung verknüpfen, werde ich diese aufgrund der interessanten Erkenntnisse zur "richtigen" machen.
Nico Schlömer
@ NicoSchlömer: Danke. Was meinst du mit Vergleich mit Gauss-Legendre? (weil die Gauß-Legendre-Gewichte maschinengenau reproduziert werden). Der Vergleich zwischen Leg. und CC wurde von Trefethen durchgeführt, mit dem Ergebnis, dass die Genauigkeit von CC oft vergleichbar ist. In der Tat wäre es interessant, die Leistung verschiedener benutzerdefinierter Gitter zu untersuchen und mit Legendre oder Clenshaw-Curtis zu vergleichen. Außerdem habe ich die am besten gewählte Antwort verlinkt.
Davidhigh
10

Sie können dies mit dem Björck-Pereyra-Algorithmus zur Lösung von Vandermonde-Systemen bewerten, da Sie bewertenbV1b=(2,0,23,0,25,0,)

0x1<x2<<xnVb0x1O(n2)Lix12(x+1)

O(ϵmach)

module VandermondeInverse

using SpecialMatrices

function main(n=8)
  X = Rational{BigInt}[k//(n-1) for k=0:n-1]
  # X = convert(Vector{Rational{BigInt}}, linspace(-1, 1, n))
  x = convert(Vector{Float64}, X)

  A = convert(Matrix{Rational{BigInt}}, Vandermonde(X))
  b = [i%2==0 ? 2//(i+1) : 0 for i=0:n-1]
  println("Norm: ", norm(A, Inf))
  println("Norm of inverse: ", norm(inv(A), Inf))
  println("Condition number: ", cond(convert(Matrix{Float64}, A)))
  ans = A'\b
  println("True answer: ", ans)

  B = convert(Matrix{Float64}, A)
  c = convert(Vector{Float64}, b)

  println("Linear solve: ", norm((B'\c - ans)./ans, Inf))

  d = vec(c')
  for k=1:n, l=n:-1:k+1
    d[l] -= x[k]*d[l-1]
  end

  for k=n-1:-1:1, l=k:n
    if l > k
      d[l] /= x[l]-x[l-k]
    end
    if l < n
      d[l] -= d[l+1]/(x[l+1] - x[l-k+1])
    end
  end
  println("Neville elimination: ", norm((d-ans)./ans, Inf))

  nothing
end

end

V = VandermondeInverse

Ausgabe:

julia> V.main(14)
Norm: 14.0
Norm of inverse: 1.4285962612120493e10
Condition number: 5.2214922998851654e10
True answer: Rational{Int64}[3202439130233//2916000,-688553801328731//52390800,19139253128382829//261954000,-196146528919726853//785862000,6800579086408939//11642400,-43149880138884259//43659000,32567483200938127//26195400,-7339312362348889//6237000,48767438804485271//58212000,-69618881108680969//157172400,44275410625421677//261954000,-2308743351566483//52390800,11057243346333379//1571724000,-209920276397//404250]
Linear solve: 1.5714609387747318e-8
Neville elimination: 1.3238218572356314e-15

Wenn dies Xnicht wie in diesem Test positiv ist, scheinen die relativen Fehler in der gleichen Größenordnung zu liegen wie bei einer regulären linearen Lösung.

bV1LiLi(xj)=δijαjkLk

Lk(x)=j,kαj,kxj=(1,x,x2,,xn)(α0k,,αnk),
L
L=(α00α0nαn0αnn).
LkL(1,x,,xn)
(1,x,x2,,xn)L=(L0(x),L1(x),,Ln(x)).
Lk(xj)=δjk
(1x0x02x0n1xnxn2xnn)L=I,
L=V1Vxj

11xkdx=1+(1)kk+1

11Lk(x)dx=jαjk1+(1)kk+1=(2,0,23,0,25,0,)(α0k,,αnk).
n+1k=0n(2,0,23,0,)LL=V1
Kirill
quelle
Danke für die ausführliche Antwort! Könnten Sie, um noch mehr Klarheit zu schaffen, detaillierter angeben, wie das Problem in die Vandermonde-Form gebracht werden kann?
Nico Schlömer
@ NicoSchlömer Klar, siehe bearbeiten. Vielen Dank für die Frage, ich hatte keine Ahnung, dass dieser Algorithmus überhaupt existiert.
Kirill
n=16n=31
@ NicoSchlömer Hm, das kann ich nicht reproduzieren: Mit dem obigen Code wird V.main(32)auf meinem Laptop in etwa einer Sekunde eine sinnvolle Antwort erzeugt (mit nur wenig Speicher). Die Zahlen sind nicht einmal so groß, der größte Zähler hat 54 Ziffern, also vermute ich, dass etwas anderes für Sie schief geht. Kannst du einen Kern posten, weil ich gespannt bin, wie es fehlschlägt?
Kirill
1
@ NicoSchlömer Wenn Sie meinen, wie BigFloat beim Drucken der relativen Fehler für die Ausgabe verwendet wird, bin ich mir nicht ganz sicher, wie die Regel lautet. Aber ich habe dafür gesorgt, dass es verwendet wird Float64für d: check with @show typeof(d). Lassen Sie mich wissen, wenn Sie weitere Probleme damit finden.
Kirill
2

Berechnen Sie zuerst die Produkte der Nominatoren und Nenner und teilen Sie sie dann einmal. Die beiden Produkte sollten in der gleichen Größenordnung liegen, damit keine signifikanten Rundungsfehler auftreten. Durch die geringere Anzahl von Gleitkommaberechnungen erhalten Sie außerdem den zusätzlichen Vorteil einer höheren Geschwindigkeit.

zap
quelle