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/polyarray/polyfit"
)

func main() {

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

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

	f := NewFitting(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.7x + 0.2x²
point[0]=(1, 6), evaluated=(1, 5.7)
point[1]=(2, 5), evaluated=(2, 5.8)
point[2]=(3, 7), evaluated=(3, 6.3)
point[3]=(4, 7), evaluated=(4, 7.2)

Index

• type Fitting
  • func NewFitting(xs, ys []float64, degree int) *Fitting
  • func (f *Fitting) Add(x, y float64)
  • func (f *Fitting) Merge(b *Fitting)
  • func (f *Fitting) Solve() []float64
  • func (f *Fitting) String() string

Examples

• Package

Types

type Fitting

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

Fitting 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 NewFitting

func NewFitting(xs, ys []float64, degree int) *Fitting

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

Since 0.1.0

func (*Fitting) Add

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

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

Since 0.1.0

func (*Fitting) Merge

func (f *Fitting) Merge(b *Fitting)

Merge two sets of sample data.

This can be done because:

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

Since 0.1.0

func (*Fitting) Solve

func (f *Fitting) 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 (*Fitting) String

func (f *Fitting) 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