Bir şekilde, değerler verildi (x,f(x)) En İyi Veri uyan belirli bir derece polinom bulmak için var mı?

Biliyorum polynomial interpolation olduğu için bulma polinom Derecesi n verilen n 1 veri noktaları, ama burada, orada çok sayıda değerleri ve bulacağız düşük dereceden polinom (en iyi doğrusal formda, en iyi ikinci dereceden, en iyi kübik, vb.). 18 *...* bir ilgisi olabilir

Daha genel olarak, benim için cevap zaman biz çok değişkenli bir fonksiyon puan gibi (x,y,f(x,y)), ... ve istiyorsunuz bulmak için en iyi polinom (p(x,y)) verilen derece değişken. (Özellikle bir polinom, eğriler veya Fourier serileri.)

Her iki teori ve kod/kütüphane (Python tercihen, ama herhangi bir dil Tamam) yararlı olacaktır.

Herkese cevaplar için teşekkürler. İşte bunları özetleme denemesi. Ben mazur gör ama çok fazla "" şeyler: en küçük kareler her şey benim için yeni bir şey yapmadan önce, hakkında hiçbir şey bilmiyordum malum

DEĞİL polinom aradeğerleme

Polynomial interpolation tam dört verilen puan geçer n 1 veri noktaları, örneğin bir küp bulma verilen derece bir polinom n uydurma. Soruda dediğim gibi, bu benim istediğim değildi istedim—ben çok puan vardı ve küçük dereceden bir polinom istedim (hangi olacak sadeceyaklaşık, şanslıydık sürece) uygun—ama bazı cevapları hakkında konuşmak için ısrar beri, onları belirtmeliyim:) Lagrange polynomial, Vandermonde matrix, vb.

En küçük kareler nedir?

"En küçük kareler" belirli bir tanımı/kriter/"metrik" "ne kadar iyi" bir polinom uyuyor. (Başkaları da var, ama bu basit olanıdır.) Bir polinom uyum sağlamaya çalıştığını söylüyor p(x,y) = bx cy dx²ey²fxy veri noktaları (x . verilen bazı ^alt>benybenZben) (burada "Zbenbenyben) ", soru). İle en küçük kareler problemi olduğunu bulmak için "en iyi" katsayıları (a,b,c,d,e,f), bu nedir küçültülmüş (tuttu "az"), "sum Kare artıklar", yani

S = &toplam;ben(bir bxbencybendxben²eyben²fxbenyben- Zben)²

Teori

Önemli olan fikir olduğuna bakarsanız S gibi bir fonksiyonun (a,b,c,d,e,f), sonra S minimized bir noktada olan gradient is 0. Bu örneğin anlamına gelir ∂S/&bölüm;f=0, yani bu

∑ben2(a &üssün; fxbenyben- Zbenxbenyben= 0

ve bir benzer denklem, b, c, d, e. Bu sadece bir&üssün doğrusal denklemler;f olduğunu unutmayın. Gaussian elimination the usual methods ile onları çözebiliriz.

Bu hala denir "doğrusal azından" istediğimiz fonksiyon ikinci dereceden bir polinom olduğundan, ancak, hala doğrusal . kareler ^em>parametreleri(a,b,c,d,e,f). Not aynı şey p(x,y) herhangi bir istediğimiz zaman çalışır "doğrusal kombinasyon"keyfifonksiyonlar fjsadece bir polinom yerine (= "monomials lineer kombinasyonu").

Kod

(Sadece değişken x — f . için tek değişkenli durumda ^alt>jmonomials x^j), Numpy polyfit: var

>>> import numpy
>>> xs = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> ys = [1.1, 3.9, 11.2, 21.5, 34.8, 51, 70.2, 92.3, 117.4, 145.5]
>>> p = numpy.poly1d(numpy.polyfit(xs, ys, deg=2))
>>> print p
       2
1.517 x   2.483 x   0.4927

Genel olarak çok değişkenli ve doğrusal en küçük kareler için SciPy var. As explained in its documentation matris gereken Bir değerler fj(xben). (Teori A. Moore-Penrose pseudoinverse bulduğu) yukarıdaki örnek İle ilgili (xbenybenZben), uydurma polinom anlamı fjbu monomials x⁽⁾y⁽⁾. Aşağıdaki en iyi ikinci dereceden (veya "derecesi = 2" satır): . değiştirirseniz başka bir derecesi en iyi polinom, bulur

from scipy import linalg
import random

n = 20
x = [100*random.random() for i in range(n)]
y = [100*random.random() for i in range(n)]
Z = [(x[i] y[i])**2   0.01*random.random() for i in range(n)]

degree = 2
A = []
for i in range(n):
    A.append([])
    for xd in range(degree 1):
        for yd in range(degree 1-xd):
            A[i].append((x[i]**xd)*(y[i]**yd)) #f_j(x_i)

c,_,_,_ = linalg.lstsq(A,Z)
j = 0
for xd in range(0,degree 1):
    for yd in range(0,degree 1-xd):
        print "   (%.2f)x^%dy^%d" % (c[j], xd, yd),
        j  = 1

yazdırır

   (0.01)x^0y^0    (-0.00)x^0y^1    (1.00)x^0y^2    (-0.00)x^1y^0    (2.00)x^1y^1    (1.00)x^2y^0

bu polinom x olduğunu keşfetti²2xy y²0.01. [Son dönem bazen -0.01 bazen de ekledik rastgele gürültü nedeniyle beklenen 0 ' dir.]

/Scipy R ve Bilgisayar Cebir Sistemleri Numpy Python için alternatifler: Sage, * Kapsamlı, Akçaağaç. Hatta Excel bunu yapmak mümkün olabilir. Numerical Recipes kendimiz yöntemlerini uygulamak (C, Fortran) anlatılır.

İlgilendiriyor

• Güçlü bir şekilde etkilemiştirnoktaları nasıl seçildiğini. x=y=range(20) rastgele noktalar yerine zorunda kalınca, her zaman 1.33 x üretti²1.33 1.33 y xy²ben her zaman x[i]=y[i], çünkü bu polinom aynı olduğunu fark edene kadar şaşırtıcı olan...,: x²2xy y²= 4x²= (4/3)(x²xy y²). Ahlaki önemli noktaları dikkatle "doğru" polinom kurtulmak için seçmek önemlidir bu yüzden Eğer tercih ederseniz (, polinom aradeğerleme için Chebyshev nodes; eğer aynı doğru için en küçük kareler olarak emin değilim seçmelisiniz.)
• Aşırı uyma: daha yüksek dereceden polinom verileri her zaman daha uygun olabilir. Değiştirirseniz degree 3 veya 4 veya 5, hala çoğunlukla tanır aynı ikinci dereceden polinom (katsayıları 0 için yüksek lisans şart) ama daha büyük derece, başlar uydurma daha yüksek dereceden polinom. Ama derecesi 6, almaktan daha büyük olsa bile n (20, 200 söylemek yerine daha fazla veri noktaları) hala ikinci dereceden polinom uyuyor. Ahlaki olan için mümkün olduğunca çok sayıda veri noktaları çekmek için yardımcı olabilir aşırı uyma, kaçınmaktır.
• Tam olarak anlamadığım numerical stability sorunlar olabilir.
• Eğer bir polinom ihtiyacın olursa, fonksiyonlar, örneğin splines (parçalı polinom) diğer türlü daha iyi uyan edinebilirsiniz.