polyfit

Documentation

Overview

Package polyfit models a polynomial y from sample points xs and ys, to minimize the squared residuals.

E.g., to fit a line `y = β₂x + β₁` with two point (1, 0) and (2, 1): The input is `xs = [1, 2], ys = [0, 1], degree=1`. The result polynomial is `y = x - 1`, e.g., `β₂ = 1, β₁ = -1`.

This package provides a incremental-fitting API, that let caller to merge two set of points efficiently.

See https://en.wikipedia.org/wiki/Least_squares#Linear_least_squares

Since 0.1.0

Example

package main

import (
	"fmt"

	. "github.com/openacid/slimarray/polyfit"
)

func main() {

	// Fit 4 points with a polynomial of degree=2,
	// the result should be:
	// y = 6.2 - 0.8x + 0.2x²
	//                                    .
	//                                  ..
	//                                 .
	//                         (3,7) ..(4,7)
	//                             ..
	//                           ..
	// .                       ..
	//  ...    (1,6)        ...
	//     ......     ......
	//           .....
	//
	//                 (2,5)

	xs := []float64{1, 2, 3, 4}
	ys := []float64{6, 5, 7, 7}

	f := NewFit(xs, ys, 2)
	poly := f.Solve()

	fmt.Printf("y = %.1f + %.1fx + %.1fx²\n",
		poly[0], poly[1], poly[2])

	for i, x := range xs {
		fmt.Printf("point[%d]=(%.0f, %.0f), evaluated=(%.0f, %.1f)\n",
			i, x, ys[i], x, evalPoly(poly, x))
	}

}

func evalPoly(poly []float64, x float64) float64 {
	rst := float64(0)
	pow := float64(1)
	for _, coef := range poly {
		rst += coef * pow
		pow *= x
	}

	return rst
}

Output:

y = 6.2 + -0.8x + 0.2x²
point[0]=(1, 6), evaluated=(1, 5.8)
point[1]=(2, 5), evaluated=(2, 5.8)
point[2]=(3, 7), evaluated=(3, 6.2)
point[3]=(4, 7), evaluated=(4, 7.2)

Index

• Variables
• type Fit
  • func NewFit(xs, ys []float64, degree int) *Fit
  • func NewFitIntRange(xStart, xEnd int, ys []float64, degree int) *Fit
  • func (f *Fit) Add(x, y float64)
  • func (f *Fit) Copy() *Fit
  • func (f *Fit) Merge(b *Fit)
  • func (f *Fit) Solve() []float64
  • func (f *Fit) String() string

Examples

• Package

Variables

var (
	// XTXCache3 is the cache of XᵀX of degree 2 with integer matrix X = [[1,0,0], [1,1,1], [1,2,4]...].
	// XTXCache3[l] is the cached XᵀX of X = [0..l], the first l integers.
	XTXCache3 [1024 + 1][]float64

	// PowCache caches x^i in PowCache[x][i].
	PowCache [1024][5]float64
)

Types

type Fit

type Fit struct {
	N      int
	Degree int
	// contains filtered or unexported fields
}

Fit models a polynomial y from sample points xs and ys, to minimizes the squared residuals. It returns coefficients of the polynomial y:

f(x) = β₁ + β₂x + β₃x² + ...

It use linear regression, which assumes f(x) is in form of:

       m
f(x) = ∑ βⱼ Φⱼ(x),   Φⱼ(x) = xʲ⁻¹
       j=1

Find β to minimize (f(xᵢ) - yᵢ)², e.g., ||Xβ - Y||² = (Xβ −Y)ᵀ(Xβ −Y) = YᵀY − YᵀXβ − βᵀXᵀY + βᵀXᵀXβ where

    | 1 x₁ x₁²... |
X = | 1 x₂ x₂²... |
    | 1 x₃ x₃²... |

β = [β₁, β₂...]ᵀ

Y = [y₁, y₂...]ᵀ

Solve for β:

∂||Xβ −Y||²
---------- = −2XᵀY + 2XᵀXβ = 0
    ∂β

Finally we get:

β = (XᵀX)⁻¹XᵀY

See https://en.wikipedia.org/wiki/Least_squares#Linear_least_squares

Since 0.1.0

func NewFit

func NewFit(xs, ys []float64, degree int) *Fit

NewFit creates a new polynomial fitting context, with points and the degree of the polynomial.

Since 0.1.0

func NewFitIntRange

func NewFitIntRange(xStart, xEnd int, ys []float64, degree int) *Fit

NewFitIntRange is similar to NewFit, except it only accept integer value for x, and the value of x must be in range [0, 1024). Integer is optimized by caching XᵀX values.

And the input must satisfies:

len(ys) == xEnd - xStart

Since 0.1.3

func (*Fit) Add

func (f *Fit) Add(x, y float64)

Add a point(x, y) into this fitting.

Since 0.1.0

func (*Fit) Copy

func (f *Fit) Copy() *Fit

Copy into a new instance.

Since 0.1.3

func (*Fit) Merge

func (f *Fit) Merge(b *Fit)

Merge two sets of sample data.

This can be done because:

|X₁|ᵀ × |X₁| = X₁ᵀX₁ + X₂ᵀX₂
|X₂|    |X₂|

Since 0.1.0

func (*Fit) Solve

func (f *Fit) Solve() []float64

Solve the equation and returns coefficients of the result polynomial. The number of coefficients is f.Degree + 1.

It tries to reduce degree of the result polynomial. Since there is a polynomial of degree n that passes exactly n+1 points.

Since 0.1.0

func (*Fit) String

func (f *Fit) String() string

String converts the object into human readable format. It includes: n: the number of points. degree: expected degree of polynomial. and two cached matrix XᵀX and XᵀY.

E.g.:

n=1 degree=3
1.000 1.000 1.000 1.000
1.000 1.000 1.000 1.000
1.000 1.000 1.000 1.000
1.000 1.000 1.000 1.000

1.000
1.000
1.000
1.000

Since 0.1.0