{"id":333,"date":"2003-08-13T00:00:00","date_gmt":"2003-08-12T22:00:00","guid":{"rendered":""},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T22:00:00","slug":"333","status":"publish","type":"post","link":"https:\/\/www.vialattea.net\/content\/333\/","title":{"rendered":"In che cosa consiste il “metodo di Bairstow” per il calcolo approssimato delle radici di un’equazione?"},"content":{"rendered":"

\n

In rete \u00e8 possibile reperire una grande quantit\u00e0 di materiale
\nsull’algoritmo di Bairstow. In questa sede commentiamo il paragrafo “Real
\nand Complex Roots of Polynomials”, dagli appunti del
\ncorso di Metodi Numerici<\/a> (formato Word, circa 900 kB) di
\nun’universit\u00e0 californiana, in cui \u00e8 possibile trovare anche
\nesempi applicativi in MatLab. <\/font><\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Sia
\nf<\/i>(x<\/i>)\u00a0=\u00a0a<\/i>0<\/sub>xn<\/sup><\/i>\u00a0+\u00a0…\u00a0+\u00a0a<\/i>n<\/i>-1<\/sub>x<\/i>\u00a0+\u00a0an<\/sub><\/i>
\nun polinomio di grado n. L’algoritmo numerico di ricerca delle radici di
\npolinomi di Bairstow \u00e8 basato sul seguente metodo. Dato un polinomio
\nquadratico
\nq<\/i>(x<\/i>)\u00a0=\u00a0x<\/i>2<\/sup>\u00a0+\u00a0ux<\/i>\u00a0+\u00a0v<\/i>
\n(dove i coefficienti u<\/i> e v<\/i> sono scelti opportunamente, come
\ndiremo poi), esistono due polinomi f’<\/i> e r<\/i> tali che <\/font><\/p>\n

f<\/i>(x<\/i>)\u00a0=\u00a0q<\/i>(x<\/i>)f’<\/i>(x<\/i>)\u00a0+\u00a0r<\/i>(x<\/i>).
\n<\/font><\/p>\n

Il polinomio f’<\/i>(x<\/i>) \u00e8 di grado
\nn<\/i>\u00a0–\u00a02 e il resto r<\/i>(x<\/i>) \u00e8 di grado 1,
\ncio\u00e8 una funzione lineare. Nel caso in cui
\nr<\/i>(x<\/i>)\u00a0=\u00a00, si avrebbe che f<\/i>(x<\/i>) \u00e8
\nun polinomio che ha due radici in comune con q<\/i>(x<\/i>). <\/font><\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Scrivendo il resto
\nr<\/i>(x<\/i>) nella forma
\nbn<\/sub><\/i>-1<\/sub>(x<\/i>\u00a0+\u00a0u<\/i>)\u00a0+\u00a0bn<\/sub><\/i>,
\ne il polinomio
\nf’<\/i>(x<\/i>)\u00a0=\u00a0b<\/i>0<\/sub>x<\/i>n<\/i>-2<\/sup>\u00a0+\u00a0…\u00a0+\u00a0b<\/i>n<\/i>-3<\/sub>x<\/i>\u00a0+\u00a0b<\/i>n<\/i>-2<\/sub>
\nsi ottiene una riscrittura di f<\/i>(x<\/i>) nei seguenti termini: <\/font><\/p>\n

\n

a<\/i>0<\/sub>xn<\/sup><\/i>\u00a0+\u00a0…\u00a0+\u00a0a<\/i>n<\/i>-1<\/sub>x<\/i>\u00a0+\u00a0an<\/sub><\/i>\u00a0=\u00a0(b<\/i>0<\/sub>x<\/i>n<\/i>-2<\/sup>\u00a0+\u00a0…\u00a0+\u00a0b<\/i>n<\/i>-3<\/sub>x<\/i>\u00a0+\u00a0b<\/i>n<\/i>-2<\/sub>)(x<\/i>2<\/sup>\u00a0+\u00a0ux<\/i>\u00a0+\u00a0v<\/i>)\u00a0+\u00a0bn<\/sub><\/i>-1<\/sub>(x<\/i>\u00a0+\u00a0u<\/i>)\u00a0+\u00a0bn<\/sub><\/i>;
\n<\/font><\/p>\n

i due polinomi, per essere uguali, devono avere gli stessi
\ncoefficienti per uguali potenze di x<\/i>. Questo fatto definisce la
\nrelazione di ricorrenza: <\/font><\/p>\n

bi<\/sub><\/i>\u00a0=\u00a0ai<\/sub><\/i>\u00a0–\u00a0b<\/i>i<\/i>-1<\/sub>u<\/i>\u00a0–\u00a0b<\/i>i<\/i>-2<\/sub>v<\/i>
\n\u00a0\u00a0\u00a0\u00a0(i<\/i>\u00a0=\u00a02,\u00a03,\u00a0…,\u00a0n<\/i>)
\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0[1] <\/font><\/p>\n

ove b<\/i>0<\/sub>\u00a0=\u00a0a<\/i>0<\/sub> e
\nb<\/i>1<\/sub>\u00a0=\u00a0a<\/i>1<\/sub>\u00a0–\u00a0b<\/i>0<\/sub>u<\/i>.
\n<\/font><\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Il problema principale
\ndel metodo di Bairstow \u00e8 scegliere i fattori u<\/i> e v<\/i> in
\nmodo tale che il resto r<\/i>(x<\/i>) sia nullo, ovvero che
\nb<\/i>n<\/i>-1<\/sub> e bn<\/sub><\/i> siano identicamente
\nnulli. Ci\u00f2 comporta la necessit\u00e0 di risolvere il sistema,
\nottenuto dalla equazione alla ricorrenze di cui sopra, <\/font><\/p>\n

<\/p>\n\n\n\n\n
b<\/i>n<\/i>-1<\/sub>(u<\/i>, v<\/i>) = 0<\/font><\/td>\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0[2]
\n <\/font><\/td>\n<\/tr>\n
bn<\/sub><\/i>(u<\/i>, v<\/i>) = 0
\n<\/font><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

<\/center><\/p>\n

Le radici del sistema possono essere ottenute mediante il
\nmetodo di Raphson-Newton per la ricerca di radici di polinomi lineari
\n(u<\/i> e v<\/i> appaiono infatti di primo grado nella equazione alle
\nricorrenze). A partire da stime iniziali di u<\/i> e v<\/i> \u00e8
\npossibile determinare piccoli incrementi \"\"\/u<\/i>, \"\"\/v<\/i> che
\nrisolvano il sistema [2], i.e.: <\/font><\/p>\n

<\/p>\n\n\n\n\n
b<\/i>n<\/i>-1<\/sub>(u<\/i> + \"\"\/u<\/i>, v<\/i> + \"\"\/v<\/i>) = 0<\/font><\/td>\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0[3]
\n <\/font><\/td>\n<\/tr>\n
bn<\/sub><\/i>(u<\/i> + \"\"\/u<\/i>, v<\/i> + \"\"\/v<\/i>) = 0
\n<\/font><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

<\/center><\/p>\n

il metodo di Raphson-Newton prevede l’espansione della [3]
\nin serie di Taylor bidimensionale in u<\/i> e v<\/i>. Per ottenere una
\nprecisione sufficiente, nella serie di Taylor ci si arresta al termine
\nlineare: <\/font><\/p>\n

\"\"\/
\n\u00a0\u00a0\u00a0\u00a0(i<\/i>\u00a0=\u00a0n<\/i>\u00a0–\u00a01,\u00a0n<\/i>)
\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0[4] <\/font><\/p>\n

L’equazione alle ricorrenze [1] \u00e8 ovviamente valida
\nanche per calcolare le derivate parziali della [4]. Ci\u00f2 consente di
\nriscrivere la [4] applicando al posto delle derivate parziali dei
\ncoefficienti numerici (vedi testo di riferimento per i dettagli) rispetto a
\ncui \u00e8 possibile risolvere il sistema [4], calcolare le derivate
\nparziali e, quindi gli incrementi \"\"\/u<\/i>, \"\"\/v<\/i>. Si
\nosservi che il sistema [4] dipende dalle stime correnti dei valori u<\/i>,
\nv<\/i>. <\/font><\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0L’algoritmo procede
\nquindi iterativamente nel modo seguente: <\/font><\/p>\n

    <\/p>\n
  1. \n

    Si scelgono u<\/i>, v<\/i> come valori iniziali.<\/p>\n<\/li>\n

  2. \n

    Si risolve il sistema [4] e si calcolano i valori
    \ncorrispondenti di \"\"\/u<\/i>, \"\"\/v<\/i> utilizzando il valore corrente di u<\/i>,
    \nv<\/i>. Se \"\"\/u<\/i>, \"\"\/v<\/i> sono prossimi allo zero, l’algoritmo termina. La
    \nprecisione delle radici trovate \u00e8 strettamente correlata alla
    \ncondizione di arresto dell’algoritmo.<\/p>\n<\/li>\n

  3. \n

    Si impostano
    \nu<\/i>\u00a0=\u00a0u<\/i>\u00a0+\u00a0\"\"\/u<\/i> e v<\/i>\u00a0=\u00a0v<\/i>\u00a0+\u00a0\"\"\/v<\/i> e si re-itera dal passo 1.<\/p>\n<\/li>\n

    <\/font><\/ol>\n

    Al termine delle iterazioni, il sistema [3] \u00e8
    \nsoddisfatto e sono determinati i valori dei coefficienti u<\/i>, v<\/i>
    \nper cui il resto r<\/i>(x<\/i>) \u00e8 nullo. A questo punto le due
    \nradici del polinomio
    \nq<\/i>(x<\/i>)\u00a0=\u00a0x<\/i>2<\/sup>\u00a0+\u00a0ux<\/i>\u00a0+\u00a0v<\/i>
    \nsono in comune con il polinomio f<\/i>(x<\/i>). Reiterando il processo
    \nper il polinomio f’<\/i>(x<\/i>) si trovano a due a due tutte le radici
    \ndi f<\/i>(x<\/i>) cercate. <\/font><\/p>\n

    \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Il metodo di Bairstow,
    \nessendo basato sull’algoritmo di Raphson-Newton, ne eredita le stesse
    \ncaratteristiche di stabilit\u00e0 e robustezza. La convergenza del metodo
    \nnon \u00e8 sempre garantita, per assicurarne il funzionamento, occorre
    \nscegliere la coppia u<\/i>, v<\/i> in modo accurato. <\/font><\/p>\n

    \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Nel link di riferimento,
    \n\u00e8 presentata la descrizione formale dell’algoritmo e vari esempi di
    \napplicazione in Matlab dei principali algoritmi numerici di ricerca degli
    \nzeri.<\/p>\n

    <\/font><\/p>\n","protected":false},"excerpt":{"rendered":"

    […]<\/p>\n","protected":false},"author":180,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[67],"tags":[],"class_list":["post-333","post","type-post","status-publish","format-standard","hentry","category-analisi-numerica"],"_links":{"self":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts\/333","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/users\/180"}],"replies":[{"embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/comments?post=333"}],"version-history":[{"count":0,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts\/333\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/media?parent=333"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/categories?post=333"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/tags?post=333"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}