Algorithmensammlung: Numerik: Horner-Schema

Algorithmensammlung: Numerik

• Dividierte Differenzen
• Hermiteinterpolation
• Horner-Schema
• Quadratur
• Gauß-Jordan-Algorithmus
• Inverse Matrix
• Determinante

Horner-Schema

Das Horner-Schema beschreibt in der numerischen Mathematik eine einfache Art, Polynome aufzuschreiben und auszuwerten.

Es nutzt aus, dass sich jedes Polynom $p(x)=b_{0}+b_{1}x+b_{2}x^{2}+\dots +b_{n}x^{n}$ schreiben lässt als $p(x)=(\dots (b_{n}x+b_{n-1})x+\dots )x+b_{0}.$.

Die verwendeten Koeffizienten $b_{n}$ lassen sich mithilfe eines Interpolationsalgorithmus bestimmen.

Für nähere Informationen über das Horner-Schema siehe  Horner-Schema.

C

double horner(double Ac[], double Ax[], int n, double x) {
    /* Ac ist der Vektor mit den Koeffizienten,
       Ax sind die Stützstellen und, n die Anzahl von Stützstellen und
       x der Punkt, an dem ausgewertet werden soll. */
    int i;
    double y = 0;
    for(i=n; i>=0; i--) {
        y = y * (x - Ax[i]) + Ac[i];
    }
    return y;
}

Ruby

# Berechnet das Ergebnis eines Polynoms mithilfe des Horner-Schemas
#
# @param z [Numeric] Stelle der Auswertung
# @param poly [Array<Numeric>] Folge der Stützstellen, in ihrem Exponenten absteigend sortiert
#
# @example Beispiel für (2x³ -x² + 4) mit x = 5
#   horner(5, [2, -1, 0, 4]) #=> 229
def horner(x, poly)
  poly.inject do |sum, k|
    (sum * x) + k
  end
end

Visual Basic .NET

    ''' <summary>
    ''' Das Horner-Schema beschreibt in der numerischen Mathematik eine einfache Art, Polynome aufzuschreiben und auszuwerten.
    ''' </summary>
    ''' <param name="Ac">Vektor mit den Koeffizienten,</param>
    ''' <param name="Ax">Stützstellen</param>
    ''' <param name="x">Der Punkt, an dem ausgewertet werden soll.</param>
    Function horner(ByVal Ac As Double(), ByVal Ax As Double(), ByVal x As Double) As Double
        Dim y As Double = 0
        For i As Integer = Ax.Length - 1 To 0 Step -1
            y *= (x - Ax(i)) + Ac(i)
        Next
        Return y
    End Function

Matlab

Siehe Octave.

Octave

function y = horner(Ac, Ax, x)
    % Ac ist der Vektor mit den Koeffizienten,
    % Ax sind die Stützstellen und
    % x der Vektor der Punkte, an denen ausgewertet werden soll.
    %
    y = zeros(length(x));
    for i = length(Ax):-1:1
        y = y .* (x - Ax(i)) + Ac(i);
    end
end

Java

/**
  @param Ac: die Koeffizienten
  @param Ax: die Stützstellen
  @param x: ein einfacher Punkt (statt ein Vektor)
*/
public static double horner(double[] Ac, double[] Ax, double x){
	double y = 1;
	for (int i = Ac.length - 1; i >= 0; i--){
		y *= (x - Ax [i]) + Ac [i];
	}
	return y;
}

/**
  @param b: Array der Koeffizienten (Exponent als Index)
  @param x: Wert der unabhängigen Variablen.
*/
public static double horner(double[] b, double x) {
	double y = 1;
	for (int i = b.length - 1; i >= 0 ; i--) {
	  y *= x + b[i];
    }
	return y;
}