Lagrange Interpolation

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Lagrange Interpolation is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

The task is to implement the Lagrange Interpolation formula and use it to solve the example problem to find a polynomial P of degree<4 satisfying P(1)=1 P(2)=4 P(3)=1 P(4)=5 as described at https://brilliant.org/wiki/lagrange-interpolation or https://en.wikipedia.org/wiki/Lagrange_polynomial

Related task Curve that touches three points

F#

```// Lagrange Interpolation. Nigel Galloway: September 5th., 2023
let symbol=MathNet.Symbolics.SymbolicExpression.Variable
let qi=MathNet.Symbolics.SymbolicExpression.FromInt32
let eval (g:MathNet.Symbolics.SymbolicExpression) x=let n=Map["x",MathNet.Symbolics.FloatingPoint.Real x] in MathNet.Symbolics.Evaluate.evaluate n g.Expression
let fN g=let x=symbol "x" in g|>List.fold(fun z c->(x-c)*z)(qi 1)
let fG(n,g)=let n,g=n|>List.map qi,g|>List.map qi in List.map2(fun i g->i,g,n|>List.except [i]) n g
let LIF n=fG n|>List.sumBy(fun(ci,bi,c)->bi*(fN c)/(c|>List.fold(fun z c->(ci-c)*z)(qi 1)))
printfn \$"%s{LIF([1;2;3;4],[1;4;1;5]).Expand().ToString()}"
```
Output:
```-21 + 215/6*x - 16*x^2 + 13/6*x^3
```

J

From the J wiki polynomial phrases page, we have a couple implementations:

```lagrange=: ] +/ .* [ (] % p.~) 1 p.@;~&1\. [
lagrange1=: %.@(^/ i.@#)@[ +/ .* ]
```

```   1 2 3 4 lagrange 1 4 1 5
_21 215r6 _16 13r6
1 2 3 4 lagrange1 1 4 1 5
_21 35.8333 _16 2.16667
```

(The J representation of a polynomial is the list of coefficients of the polynomial such that the index of the coefficient is the power applied to the polynomial's variable.)

jq

Works with: jq

Works with gojq, the Go implementation of jq

With minor modifications related to the module system, the program presented here also works with jaq, the Rust implementation of jq

The function `lagrange/1` is adapted from Wren.

This entry uses the "polynomials" module in which a polynomial is represented by the JSON array comprised of the polynomial's coefficients, with the entry at .[i] corresponding to the coefficient of x^i. The canonical form of a polynomial of degree n is represented by an array of length n+1.

```include "polynomials" {search: "./"};

# Returns the Lagrange interpolating polynomial which passes through a list of points.
def lagrange(\$pts):
(\$pts|length) as \$c
| reduce range(0;\$c) as \$i ({polys: []};
.poly = [1]
| reduce range(0;\$c) as \$j (.;
if (\$i != \$j)
then .poly = (multiply(.poly; [-\$pts[\$j][0], 1]))
else .
end )
| (.poly | eval(\$pts[\$i][0])) as \$d
| .polys[\$i] = (.poly | scalarDivide(\$d)) )
| reduce range(0;\$c) as \$i (.sum = [0];
.polys[\$i] = (.polys[\$i] | scalarMultiply(\$pts[\$i][1]))
| .sum = add(.sum; .polys[\$i]) )
| .sum ;

def pts: [
[1, 1],
[2, 4],
[3, 1],
[4, 5]
];

lagrange(pts) | pp```
Output:
```2.1666666666666665x³-16.0x²+35.83333333333333x-21.0
```

Julia

Note the Polynomials module prints polynomials in order from degree 0 to n rather than n to zero degree.

```using Polynomials, SpecialPolynomials

const pts = [[1, 1], [2, 4], [3, 1], [4, 5]]
const xs = first.(pts)
const ys = last.(pts)
const p = Lagrange(xs, ys)

@show p Polynomial(p)
```
Output:
```p = Lagrange(1⋅ℓ_0(x) + 4⋅ℓ_1(x) + 1⋅ℓ_2(x) + 5⋅ℓ_3(x))
Polynomial(p) = Polynomial(-21.0 + 35.83333333333333*x - 16.0*x^2 + 2.1666666666666665*x^3)
```

```using Polynomials

function Lagrange(pts::Vector{Vector{Int}})
xs = first.(pts)
cs = last.(pts)
n = length(xs)
n == 1 && return Polynomial(cs[1])
arr = ones(Int, n)
for j in 2:n
for k in 1:j
arr[k] = (xs[k] - xs[j]) * arr[k]
end
arr[j] = prod(xs[j] - xs[i] for i in 1:(j - 1))
end
ws = 1 .// arr
q = Polynomial(0 // 1)
x = variable(q)
for i in eachindex(ws)
m = prod(x - xs[j] for j in eachindex(xs) if j != i)
q += m * ws[i] * cs[i]
end
return q
end

const testpoints = [[1, 1], [2, 4], [3, 1], [4, 5]]
@show Lagrange(testpoints)
```
Output:
```Lagrange(testpoints) = Polynomial(-21//1 + 215//6*x - 16//1*x^2 + 13//6*x^3)
```

Phix

Translation of: Wren
```with javascript_semantics
integer l1 = length(p1),
l2 = length(p2)
if l2>l1 then p1 &= repeat(0,l2-l1) end if
for i=1 to l2 do
p1[i] += p2[i]
end for
return p1
end function

function mul_poly(sequence p1,p2)
integer m = length(p1),
n = length(p2)
sequence res = repeat(0,m+n-1)
for i=1 to m do
for j=1 to n do
res[i+j-1] += p1[i]*p2[j]
end for
end for
return res
end function

function scalar_multiply(sequence poly, atom x)
return sq_mul(poly,x)
end function

function sclar_divide(sequence poly, atom x)
return sq_div(poly,x)
end function

function eval_poly(sequence poly, atom x)
integer c = length(poly)
atom res = poly[\$]
for i=length(poly)-1 to 1 by -1 do
res = res*x + poly[i]
end for
return res
end function

procedure show_poly(sequence poly)
integer l = length(poly)
for i=l to 1 by -1 do
atom p = poly[i]
if i<l then
puts(1,iff(p<0?" ":" +"))
end if
printf(1,"%g",p)
if i>1 then
puts(1,"x")
if i>2 then
printf(1,"^%d",i-1)
end if
end if
end for
puts(1,"\n")
end procedure
constant show = show_poly

enum X, Y
function lagrange(sequence pts)
// Returns the Lagrange interpolating polynomial which passes through a list of points.
integer c = length(pts)
sequence polys = repeat(null,c)
for i=1 to c do
sequence poly = {1}
for j=1 to c do
if i!=j then
poly = mul_poly(poly,{-pts[j][X],1})
end if
end for
atom d = eval_poly(poly,pts[i][X])
polys[i] = sclar_divide(poly,d)
end for
sequence res = {0}
for i=1 to c do
polys[i] = scalar_multiply(polys[i],pts[i][Y])
end for
return res
end function

constant pts = {{1,1},{2,4},{3,1},{4,5}}
sequence lip = lagrange(pts)
show(lip)
```
Output:
```2.16667x^3 -16x^2 +35.8333x -21
```

Raku

Translation of: Wren
```# 20231020 Raku programming solution

class Point { has (\$.x, \$.y) }

sub add(@p1, @p2) { return @p1 <<+>> @p2 } # Add two polynomials.

sub multiply(@p1, @p2) { # Multiply two polynomials.
my (\$m,\$n) = (@p1,@p2)>>.elems;
my @prod   = [ 0 xx \$m + \$n - 1 ];
for ^\$m X ^\$n -> (\$i,\$j) { @prod[\$i+\$j] += @p1[\$i] * @p2[\$j] }
return @prod;
}

# Multiply a polynomial by a scalar.
sub scalarMultiply(@poly, \$x) { return @poly.map: * × \$x }

# Divide a polynomial by a scalar.
sub scalarDivide(@poly, \$x) { return scalarMultiply(@poly, 1/\$x) }

# rosettacode.org/wiki/Horner%27s_rule_for_polynomial_evaluation#Raku
sub evalPoly(@coefs, \$x) { return ([o] map { \$_ + \$x × * }, @coefs.reverse)(0) }

sub lagrange(@pts) {
my (\$c, @polys) = @pts.elems;
for ^\$c -> \$i {
my @poly = 1;
for ^\$c -> \$j {
next if \$i == \$j;
@poly = multiply @poly, [ -@pts[\$j].x, 1 ]
}
@polys[\$i] = scalarDivide @poly, evalPoly(@poly.reverse, @pts[\$i].x)
}
my @sum = 0;
for ^\$c -> \$i { @sum = add @sum, scalarMultiply @polys[\$i], @pts[\$i].y }
return @sum;
}

my @pts = [<1 1>,<2 4>,<3 1>,<4 5>].map: { Point.new: x => .[0], y => .[1] };

say [~] lagrange(@pts).kv.rotor(2).reverse.map: -> (\$expo,\$coef) {
"{ '+' if \$coef ≥ 0 }\$coef" ~ do given \$expo {
when 0  { " " }
when 1  { "𝑥 " }
default { "𝑥^\$_ " }
}
}
```

You may Attempt This Online!

RPL

Works with: HP version 49
```[[1 2 3 4][1 4 1 5]] LAGRANGE
```
Output:
```1: '(13*X^3-96*X^2+215*X-126)/6'
```

Wren

Library: Wren-dynamic
Library: Wren-math
Library: Wren-fmt

A polynomial is represented here by a list of coefficients from the lowest to the highest degree. However, the library methods which deal with polynomials expect the coefficients to be presented from highest to lowest degree so we therefore need to reverse the list before calling these methods.

```import "./dynamic" for Tuple
import "./math" for Math
import "./fmt" for Fmt

var Point = Tuple.create("Point", ["x", "y"])

var add = Fn.new { |p1, p2|
var m = p1.count
var n = p2.count
var sum = List.filled(m.max(n), 0)
for (i in 0...m) sum[i] = p1[i]
for (i in 0...n) sum[i] = sum[i] + p2[i]
return sum
}

// Multiply two polynmials.
var multiply = Fn.new { |p1, p2|
var m = p1.count
var n = p2.count
var prod = List.filled(m + n - 1, 0)
for (i in 0...m) {
for (j in 0...n) prod[i+j] = prod[i+j] + p1[i] * p2[j]
}
return prod
}

// Multiply a polynomial by a scalar.
var scalarMultiply = Fn.new { |poly, x| poly.map { |coef| coef * x }.toList }

// Divide a polynomial by a scalar.
var scalarDivide = Fn.new { |poly, x| scalarMultiply.call(poly, 1/x) }

// Returns the Lagrange interpolating polynomial which passes through a list of points.
var lagrange = Fn.new { |pts|
var c = pts.count
var polys = List.filled(c, null)
for (i in 0...c) {
var poly = [1]
for (j in 0...c) {
if (i == j) continue
poly = multiply.call(poly, [-pts[j].x, 1])
}
var d = Math.evalPoly(poly[-1..0], pts[i].x)
polys[i] = scalarDivide.call(poly, d)
}
var sum = [0]
for (i in 0...c) {
polys[i] = scalarMultiply.call(polys[i], pts[i].y)
}
return sum
}

var pts = [
Point.new(1, 1),
Point.new(2, 4),
Point.new(3, 1),
Point.new(4, 5)
]
var lip = lagrange.call(pts)
Fmt.pprint("\$f", lip[-1..0], "", "x")
```
Output:
```2.166667x³ - 16.000000x² + 35.833333x - 21.000000
```