math — генерирует интерполяционную функцию из точек переполнения стека
Мне нужно сделать скрипт PHP, который генерирует функцию интерполяции из набора точек.
Я решил использовать интерполяцию Лагранжа, потому что мне было проще всего найти пример, который генерирует функцию из списка входных точек. Проблемы с другими методами в том, что я не смог найти пример, который генерирует функцию -> все остальные примеры для всех других интерполяций генерируют только дополнительные точки, а не функцию из существующих точек.
Источник, который я использовал, чтобы найти пример для интерполяции Лагранжа: http://www2.lawrence.edu/fast/GREGGJ/Math420/Section_3_1.pdf
Я решил повторить этот пример в своем коде PHP.
/**
* Generate one basis polynomial function
* @param type $points array of points
* @param type $basisPolynomial Each basis polynomial will be stored in the array of values so that it can be appended to the final function
* @param type $allXValues all x values for the point
* @param type $i current index of the basis polynomial
*/
function generateBasisPolynomial(&$basisPolynomial, $allXValues, $i) {
$basisPolynomial[$i] = "(";
$divisor = "(";
for ($j = 0; $j < count($allXValues); $j++) {
if ($j == $i) {
continue;
}
$basisPolynomial[$i] .= "(x-$allXValues[$j])*";
$divisor .="($allXValues[$i]-$allXValues[$j])*";
}
//multiply the divisor by 1, because the previous loop has * at the end of the equation
$divisor .="1)";
$basisPolynomial[$i] .="1)/$divisor";
}
/**
* Function that generates the Lagrange interpolation from the list of points
* @param type $points
* @return string
*/
function generateLagrangeInterpolation($points) {
$numberOfPoints = count($points);
if ($numberOfPoints < 2) {
return "NaN";
} else {
//source http://www2.lawrence.edu/fast/GREGGJ/Math420/Section_3_1.pdf
//for each point, construct the basis polynomial
//for a sequence of x values, we will have n basis polynomials,
//Example:
//if we, for example have a sequence of four points, with their sequence of x values being {x0,x1,x2,x3}
//then we construct the basis polynomial for x0 by doing the following calculation:
//F(x) = ((x-x1)*(x-x2)*(x-x3))/((x0-x1)*(x0-x2)*(x0-x3)) -> where x is an unknown variable.
$basisPolynomial = array();
//get all x values from the array of points so that we can access them by index
$allXValues = array_keys($points);
$allYValues = array_values($points);
//Because the Y values are percentages, we want to divide them by 100.
$allYValues = array_map(function($val) {
return $val / 100;
}, $allYValues);
$returnFunction = "";
for ($i = 0; $i < $numberOfPoints; $i++) {
generateBasisPolynomial($basisPolynomial, $allXValues, $i);
//multiply this basis polynomial by y value
$returnFunction .="$allYValues[$i]*$basisPolynomial[$i]+";
}
//Append 0 to the end of the function because the above loop returns a function with a +
//at the end so we want to make it right
$returnFunction .="0";
echo $returnFunction;
}
}
//$points = array("4.1168" => "0.213631", "4.19236" => "0.214232", "4.20967" => "0.21441", "4.46908" => "0.218788");
$points = array("0.1" => "5", "0.3" => "10", "0.5" => "30", "0.6" => "60", "0.8" => "70");
generateLagrangeInterpolation($points);
В результате я получаю следующую функцию:
0.05*((x-0.3)*(x-0.5)*(x-0.6)*(x-0.8)*1)/((0.1-0.3)*(0.1-0.5)*(0.1-0.6)*(0.1-0.8)*1)+0.1*((x-0.1)*(x-0.5)*(x-0.6)*(x-0.8)*1)/((0.3-0.1)*(0.3-0.5)*(0.3-0.6)*(0.3-0.8)*1)+0.3*((x-0.1)*(x-0.3)*(x-0.6)*(x-0.8)*1)/((0.5-0.1)*(0.5-0.3)*(0.5-0.6)*(0.5-0.8)*1)+0.6*((x-0.1)*(x-0.3)*(x-0.5)*(x-0.8)*1)/((0.6-0.1)*(0.6-0.3)*(0.6-0.5)*(0.6-0.8)*1)+0.7*((x-0.1)*(x-0.3)*(x-0.5)*(x-0.6)*1)/((0.8-0.1)*(0.8-0.3)*(0.8-0.5)*(0.8-0.6)*1)+0
Мне все равно, что выражение упрощено и рассчитано полностью (однако, если у вас есть какой-либо совет или код, который мог бы сделать это для меня, это было бы огромным плюсом).
Если я посмотрю на упрощенное выражение, оно выглядит примерно так:
(47500*x^4-79300*x^3+42245*x^2-8699*x+480)/(-840)
Однако, если я попытаюсь вставить эту функцию в http://fooplot.com -> Я понял, что график проходит через точки, определенные как входные параметры, однако я не уверен, что график для других точек правильный, так как похоже, что значения Y переходят в минус, когда X <= 0 или x> = 1.
Советуете ли вы использовать другую функцию или можно уменьшить существующую ошибку в интерполяции, если бы у меня было больше входных точек? Я должен быть честным, что я плохой математик, поэтому любой реальный пример более точного метода или пример в коде будет принята с благодарностью.
Спасибо
Решение
Вот что вы можете попробовать:
function basisPolynomial($points, $j, $x) {
$xj = $points[$j][0]; //Assume a point is an array of 2 numbers
$partialProduct = 1;
//Product loop
for ($m = 0;$i < count($points);$m++) {
if ($m === $j) { continue; }
$partialProduct *= ($x - $points[$m][0])/($xj-$points[$m][0]);
}
return $partialProduct;
}
function lagrangePolynomial($points,$x) {
$partialSum = 0;
for ($j = 0;$j < count($points);$j++) {
$partialSum += $points[$j][1]*basisPolynomial($points,$j,$x);
}
return $partialSum;
}
Теперь, если вам нужно построить его, вы можете создать список точек, которые можно использовать в функции построения графика, например,
$points = <my points>;
$plotPoints = [];
for ($i = 0;$i < 10;$i+= 0.1) { //for example
$plotPoints[] = [ $i, lagrangePolynomial($points,$i) ];
}
Если вы хотите просто использовать для прямого построения графика, вам нужно использовать инструмент построения, такой как gnuplot, чтобы определить функции и заставить их определять, как их наносить.
Обновить: http://www.physics.brocku.ca/Courses/5P10/lectures/lecture_10_handout.pdf Кажется, у gnuplot есть пример того, что вам нужно, но это похоже на обман
Другие решения
Я не очень знаком с объектно-ориентированной реализацией php, но в Java я делаю этого маленького ребенка;)
import java.util.*;
import java.util.Arrays;
import java.util.List;
public class Run{
public static void main(String[] args){
int[] parameters = new int[]{-1, 2, 4, 3};
Binom b = new Binom(1, 1, parameters[1], 0);
Polinom p = new Polinom(b);
for(int i = 2; i < parameters.length; i++)
p.joinBinom(new Binom(1, 1, -1 * parameters[i], 0));
System.out.println(p.toString() + " / (" + getDenominator(parameters) + ")");
}
public static int getDenominator(int[] params){
int result = 1;
for(int i = 1; i < params.length; i++)
result *= params[0] - params[i];
return result;
}
}
class Monomial{
private int constant = 1;
private int pow = 0;
public int getConstant(){
return this.constant;
}
public void sumConstant(int value){
this.constant += value;
}
public boolean hasVariable(){
return this.pow > 0;
}
public int getPow(){
return this.pow;
}
public Monomial(int constant, int pow){
this.constant = constant;
this.pow = pow;
}
public ArrayList<Monomial> multiply(Binom a){
Monomial first = new Monomial(this.constant * a.getFirst().getConstant(), this.pow + a.getFirst().getPow());
Monomial second = new Monomial(this.constant * a.getSecond().getConstant(), this.pow + a.getSecond().getPow());
System.out.print("\t" + this.toString() + "\t* (" + a.getFirst().toString() + " " + a.getSecond().toString() + ")");
System.out.print("\t= " + first.toString() + "\t");
System.out.println(second.toString());
return (new Binom(first, second)).toList();
}
public String toString(){
String result = "";
if(this.constant == 1){
if(!this.hasVariable())
result += this.constant;
}
else
result += this.constant;
if(this.hasVariable()){
result += "X";
if(this.pow > 1)
result += "^" + this.pow;
}
return result;
}
}
class Binom{
private Monomial first;
private Monomial second;
public Monomial getFirst(){
return this.first;
}
public Monomial getSecond(){
return this.second;
}
public Binom(int constant1, int pow1, int constant2, int pow2){
this.first = new Monomial(constant1, pow1);
this.second = new Monomial(constant2, pow2);
}
public Binom(Monomial a, Monomial b){
this.first = a;
this.second = b;
}
public ArrayList<Monomial> toList(){
ArrayList<Monomial> result = new ArrayList<>();
result.add(this.first);
result.add(this.second);
return result;
}
}
class Polinom{
private ArrayList<Monomial> terms = new ArrayList<>();
public Polinom(Binom b){
this.terms.add(b.getFirst());
this.terms.add(b.getSecond());
}
private void compact(){
for(int i = 0; i < this.terms.size(); i++){
Monomial term = this.terms.get(i);
for(int j = i + 1; j < this.terms.size(); j++){
Monomial test = this.terms.get(j);
if(term.getPow() == test.getPow()){
term.sumConstant(test.getConstant());
this.terms.remove(test);
j--;
}
}
}
}
public void joinBinom(Binom b){
ArrayList<Monomial> result = new ArrayList<>();
for(Monomial t : this.terms){
result.addAll(t.multiply(b));
}
this.terms = result;
this.compact();
}
public String toString(){
String result = "";
for(Monomial t : this.terms)
result += (t.getConstant() < 0 ? " " : " +") + t.toString();
return "(" + result + ")";
}
}
которые возвращаются:
X * (X -4) = X^2 -4X
2 * (X -4) = 2X -8
X^2 * (X -3) = X^3 -3X^2
-2X * (X -3) = -2X^2 6X
-8 * (X -3) = -8X 24
( +X^3 -5X^2 -2X +24) / (-60)
Похоже, текущий алгоритм для метода интерполяции Лагранжа дает правильные результаты. Чтобы исправить ошибки в расчетах, можно указать больше базовых точек. Кроме того, чтобы умножить неизвестные переменные в математической функции, в одном из ответов был оставлен пример функции.
Спасибо всем.