viernes, 3 de marzo de 2017

método Bairstow

Otro método numérico: Bairstow.
Llamado en honor a su creador, Leonard Bairstow, tras publicarlo por primera vez en el libro Applied Aerodynamics de 1920.

Leonard Bairstow
Video explicativo:
¿Cómo funciona? Antes que nada, Bairstow es un método abierto: necesita 2 estimaciones iniciales, pero no es necesario que éstas encierren a la raíz en lo absoluto.
Todo comienza con un polinomio. Lo que hace este método es ir reduciendo el grado del polinomio 2 grados a la vez a través de divisiones sintéticas dobles.
Gracias a estas divisiones sintéticas, podremos formular un sistema de ecuaciones de 2 incógnitas donde a través del método Cramer (del cual hablaremos más a detalle en otro post), y obtener factores del polinomio original.
Con todos estos factores, se obtendrán las raíces del polinomio original.
Cuando encontremos un factor por el cual dividamos el polinomio original y nos resulte en un polinomio de grado 1 ó 0, significa que ya tenemos suficientes factores para encontrar todas las raíces.



Ahora bien, ¿bajo qué criterio determinamos que la división sintética resulte en un polinomio dos grados menor? Aquí es donde se encuentra nuestro margen de error: qué tan cercanos están los 2 valores de menor grado del resultado de la división sintética a cero. Cuando se acercan lo suficiente, los consideramos como 0 y entonces el resultado de la división sintética tiene es 2 grados menor. Por último, si el resultado es de grado 1 ó 0, significa que hemos encontrado todos los factores del polinomio original. Las raíces de cada uno de estos factores conforman nuestra respuesta final.
Código fuente en C++, con la función (x^5)-(3.5x^4)+(2.75x^3)+(2.125x^2)-(3.875x)+1.25:

 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <cmath>

using namespace std;
double EPSILON = 0.01;

void sinteticWeirdFormula( double *arr, double *arrOr, int size, double r, double s ) {
    arr[size-1] = arrOr[size-1];
    arr[size-2] = arr[size-1] * r + arrOr[size-2];
    
    for ( int i = size - 3; i >= 0; i-- ) {
        arr[i] = ( arr[i + 1] * r ) + ( arr[i + 2] * s ) + arrOr[i];
    }
    return;
}

int main() {
    double arrVal[] = {1.25, -3.875, 2.125, 2.75, -3.5, 1}; // Coeficientes del polinomio
                    //  0       x1     x2    x3    x4   x5
    int size = sizeof(arrVal) / sizeof(arrVal[0]);
    int count = 1;
    
    double arrB[size]; //Initial array B
    double arrC[size]; //Initial array C
    
    double r = -1;
    double s = -1;
    
    double dr; //delta r
    double ds; //delta s
    
    do {
        sinteticWeirdFormula( arrB, arrVal, size, r, s );
        sinteticWeirdFormula( arrC, arrB, size, r, s );
        /** Cramer
         * A = arrC[2]
         * B = arrC[3]
         * C =  - arrB[1]
         * P = arrC[1] 
         * Q = arrC[2]
         * R = - arrB[0]
         * dr = (CQ - BR) / (AQ - PB)
         * ds = (AR - CP) / (AQ - PB)
        */
        dr = ( -arrB[1] * arrC[2] - arrC[3] * -arrB[0] ) / ( arrC[2] * arrC[2] - arrC[1] * arrC[3] );
        ds = ( -arrB[0] * arrC[2] - arrC[1] * -arrB[1] ) / ( arrC[2] * arrC[2] - arrC[1] * arrC[3] );
        
        double errorR = ( dr / r ) * 100;
        double errorS = ( ds / s ) * 100;
        
        if ( abs(errorR) <= EPSILON && abs(errorS) <= EPSILON ) {
            break;
        }
        r += dr;
        s += ds;
        count++;
    } while (true);
    
    double x1 = ( r + sqrt( r * r + 4 * s ) ) / 2;
    double x2 = ( r - sqrt( r * r + 4 * s ) ) / 2;
    
    cout << "Root 1: " << x1 << endl
    << "Root 2: " << x2 << endl;
    
    cout << "r: " << r << endl
    << "s: " << s << endl;
    
    for ( int i = 0; i < size; i++ ) {
        cout << "Coeficientes de la funcion con menor grado " << arrC[i] << endl;
    }
    /*for ( int i = 0; i < size; i++ ) {
        cout << "b: " << arrB[i] << endl;
    }*/   
    return 0;
}


Ahora bien, debemos también de considerar que este método no funciona para funciones trascendentales, ni polinomios con coeficientes complejos. También, si se le da una precisión demasiado pequeña, Bairstow puede tener divergencia.

 Ahora que hemos analizado a detalle este método, podemos ver cómo aunque este método cuenta con ventajas muy grandes como no necesitar la derivada de la función como en Newton-Raphson y permitirnos encontrar más de una raíz (incluso imaginarias), sigue sin ser un método perfecto para todos los casos. Lo importante es tomar la mejor decisión sobre qué método usar para cada caso específico.
Fuentes:

Publicado por en

No hay comentarios:

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)