Räkna ut funktionen för en andragradsfunktion

Låt säga att vi har 3 punkter på ett koordinatsystem som följer kurvan för en viss andragradsfunktion, hur räknar vi ut funktionen för denna linje?

Det beror på vilka punkter du har. Du får specificera punkterna mer i sådana fall. Har du bara tre godtyckliga punkter är det inte säkert att det går.

punkter tillhands: (a1,b1), (a2,b2), (a3,b3)

antag: f(x) = C*x^2 + D*x +E

ekvationssystem:

b1 = C*a1^2 + D*a1 +E
b2 = C*a2^2 + D*a2 +E
b3 = C*a3^2 + D*a3 +E

Vi har tre ekvationer och tre obekanta. Dock går det ej att lösa genom matris-radreduktion pga C-termen är olinjär.

hmm juste ja. Nej grejen är att jag försöker slå ihjäl lite tid genom att skapa ett simpelt ritprogram där jag tänkte lägga in ett verktyg liknande pen tool i illustrator.

Efter lite mysigt googlande hittade jag denna funktion för beizer-kurvor:
P(t) = (1-t)^3P0 + 3(1-t)^2tP1 + 3(1-t)t^2P2 + t^3P3 vilket (förhoppningsvis) är allt jag behöver.

Den gode Lagrange ger oss

f(x) = y(x-x1)(x-x2)/(x0-x1)(x0-x2)+y1(x-x0)(x-x2)/(x1-x0)(x1-x2)+y2(x-x0)(x-x1)/(x2-x0)(x2-x1)

för punkterna (x0,y0),(x1,y1) och (x2,y2).

Beizer-kurvorna täcker bara två punkter, den andra och tredje termen är så kallade control points. Dessutom är de bara avsedda för 0<=t<=1. EulerBoys lösning med lagrages metod är bra.Ett annat tillvägagångssätt, som kallas newton devided difference, kommer ge exakt samma polynom, fast beräkningarna är lite snabbare. Orsaken till att det ger samma polynom är att det bara finns ett enda polynom av graden n-1eller mindre som interpolerar n punkter i planet. Om vi kallar de 3 punkterna (x_0,y_0), (x_1,y_1), (x_2,y_2) så börjar man att ställa upp:
x_0 | y_0
x_1 | y_1
x_2 | y_2
i nästa steg beräknar man (y_1 - y_0) / (x_1 - x_0) som vi kan kalla a och skriver
x_0 | y_0
x_1 | y_1 | a
x_2 | y_2 | b
där b beräknats på samma sätt fast med (y_2 - y_1) / (x_2 - x_1)
slutligen beräknas c i
x_0 | y_0
x_1 | y_1 | a
x_2 | y_2 | b |c
som (b-a) / (x_2 - x_0).
Polynomet kan sedan skrivas som y_0 + a(x-x_0) + b(x-x_0)(x-x_1)
Två andra fördelar med divided difference över lagrange: kan enkelt lägga till punkter (i lagrange måste allting räknas om), och bättre condition number for systemmatrisen vid datorlösning (i lagrange utgör den en vandemonde matris).
EDIT: såg nu att du ska göra något ritverktyg (ingen erfarenhet av illustrator dock) och då är det bezier-kurvor som brukar användas. Man anger två startpunkter och 2 kontrollpunkter. Första kontrollpunkten är kopplad till startpunkten och påverkar hur kurvan beter sig när den lämnar startpunkten. Om man ser det som en vektor från P_0 till P_1 så avgör riktningen på vektorn kurvans initiala lutning, och längden på vektorn hur länge kurvan följer den riktningen innan den börjar vika av och påverkas av den andra kontrollpunkten som bestämmer hur kurvan ska bete sig när den går mot slutpunkten.

Det finns många sätt att åstadkomma detta. När det bara är 3 punkter och ett polynom vars högsta exponent är 2 så spelar det egentligen ingen roll prestandamässigt vilken metod man använder, speciellt inte då det rör sig om något så manuellt som ett ritverktyg. Alltså skulle jag personligen rekommendera den som är enklast att implementera.

Ifall prestanda trots allt är av vikt kan jag faktiskt inte svara på vilken som är mest effektiv; MATLAB ger ganska skeva resultat. Däremot kan jag säga att Nevilles metod är den absolut enklaste att implementera rent kodmässigt; iallafall av de som jag implementerat.


Kort kodförklaring: yvärde(i) står alltså för y-värdet från punkt i. Likaså med xvärde(i), det innebär x-värdet från punkt i. De x som finns i koden, alltså de som inte har något index, är alltså ett uttryck för x-et i polynomet; t.ex. a*x^2.

Det här är alltså en rekursiv kod, väldigt nätt och fin, den är dessutom uppdelad bara för klarhetens skull, "result" behöver inte ha 3 rader utan kan skrivas på en enda (de 3 result efter if-satsen). Det här kallas i vilket fall som helst Neville's algorithm och den finns på wikipedia om du vill förstå hur den fungerar.

Lite länkar till olika metoder:
http://en.wikipedia.org/wiki/Neville's_algorithm
http://en.wikipedia.org/wiki/Lagrange_interpolation
http://en.wikipedia.org/wiki/Lagrang..._interpolation (förfining av lagrange-metoden)
http://mathworld.wolfram.com/AitkenInterpolation.html http://en.wikipedia.org/wiki/Newton_polynomial

Det går visst lösa. Det här systemet är skitlinjärt. Det är bara att lösa ut, CDE ur:

[a1^2, a1, 1] [C] = [b1]
[a2^2, a2, 1]*[D] = [b2]
[a3^2, a3, 1] [E] = [b3]

Jag glömde nämna att funktionen måste kallas med parametrarna 1 och n - alltså neville(1,n) - där n är antal punkter (3 i ditt fall).

Exempel:

xvärde(1) = 1;
xvärde(2) = 5;
xvärde(3) = 27;

yvärde(1) = 1;
yvärde(2) = 25;
yvärde(3) = 729;

neville(1,3) kommer då ge svaret x^2 (om du förenklar uttrycket som blir resultatet).