El mètode Newton

Hola, en el vídeo anterior vam introduir el Mètode de Newton, destacant que serveix per calcular els zeros de funcions complexes, explicant el seu funcionament de manera gràfica, i deduint-ne la fórmula general. Tot i així, vam veure que quedaven algunes qüestions importants per resoldre, com per exemple, quantes iteracions s’han de fer per a obtenir un bon resultat o quin valor de X0 hem de triar. Però abans de continuar amb aquestes qüestions resoldrem les preguntes que vam formular al final de l'apartat 1.

En que consisteix el Mètode Newton? És un mètode numèric iteratiu que aproxima les arrels de funcions complexes mitjançant la linealització d’aquestes funcions en punts propers a l’arrel.

Dibuixeu una funció complexa que talli l’eix X en aproximadament x=1 i, agafant x0=3, itereu el mètode de Newton gràficament tres vegades. X3 us ha quedat més a prop de X* que X0?

Aquest és un exemple en el qual es pot veure com, a mesura que iterem el mètode, cada vegada s’aproxima millor l’arrel. En aquest cas, confirmem que X3 està més a prop de X* que X0. Però pot ser que alguns de vosaltres hagueu dibuixat una funció on el Mètode de Newton no us hagi funcionat adequadament. No vol dir que l’hagueu aplicat malament, en aquest cas es diu que el Mètode de Newton divergeix en l’entorn de cerca de l’arrel, i en aquest cas X0 està més a prop de X* que X3. Per a que això no ens passi, existeix una Condició de Convergència que s’haurà de satisfer si volem que el Mètode de Newton funcioni adequadament. Més endavant, en aquest vídeo, l’explicarem amb més detall.

Calcula tres iteracions del Mètode de Newton (numèricament) de la funció f(x)=x^3+x+1 agafant x0=-0,5.

En aquest cas l'aplicació numèrica seria la següent:

X1 = 2 – f(2)/f`(2) = 2,1000000

X2 = 2,1 – f(2,1)/f’(2,1) = 2,0945691211

X3 = 2,094551482

Què creieu que passaria si f’(x)=0 en alguna x?

És com si hi hagués un punt estacionari en l’entorn de cerca de l’arrel. Com es veu a la fórmula general, la derivada es troba en el denominador i, per tant, si fos igual a 0, la Xk que s’estigués calculant no existiria i per tant el Mètode de Newton deixaria de funcionar. Aquesta serà una altra situació que s’haurà de tenir en compte a l’hora de definir la Condició de Convergència del Mètode.

Abans d’entrar en detall a explicar la Condició de Convergència, anem a veure quins són els Criteris d’aturada del Mètode. És a dir com podem definir quantes vegades s’haurà d’iterar la fórmula general deduïda en el vídeo anterior. Ja hem vist que si es fa manualment, pararem d’iterar quan veiem que la Xk té la precisió desitjada, per exemple, en funció dels decimals que variïn entre xk i Xk-1. Però el Mètode de Newton s’acostuma a programar a l’ordinador, i, per tant, hem de tenir alguna manera de limitar la recurrència del mètode.

Per fer-ho cal entendre primer què són l'Error relatiu i l'Error absolut.

Definició: l’error absolut i l’error relatiu entre dues iteracions successives Xk-1 i xk són, respectivament:

ek = |xk-Xk-1| i Ek = ek/|xk| = | (xk-xk-1)/xk|

Que, per a alguna de les iteracions, Ek0 és una tolerància prefixada per l’usuari. Una alternativa d’aquest Criteri seria ek

Que, per a alguna de les iteracions, |f(Xk)|

Si, al capdavall estem buscant un zero d’f, podem aturar els càlculs quan f(Xk) sigui prou proper a 0.

Que s’hagi arribat a K = Kmax, on Kmax és un nombre d’iteracions màxim prefixat per l’usuari. Aquest criteri és fa servir gairebé sempre al principi per si, en algun cas concret, la recurrència no convergís a cap solució i per tant l’algoritme entrés en un bucle infinit. Tot i això, també es pot fer sistemàticament un nombre d’iteracions prefixat, sense haver de comprovar cap altre criteri en cada iteració.

Anem a veure ara la part del Mètode de Newton que us dóna més mal de caps. Com triar un X0 adequadament i quines condicions s’han de complir per a que el Mètode de Newton convergeixi en l’interval de cerca [a, b]. Primer de tot heu d’entendre que l’interval de cerca [a,b] correspon a tots els valors de x possibles que poden tenir les Xk. Com ja hem vist fins ara, a mesura que augmentem les iteracions, si el Mètode funciona correctament, les Xk s’aniran apropant a X*, i per tant X0 podria ser un dels extrems d’aquest interval. Reviseu les gràfiques anteriors si no enteneu aquest punt ja que és força important.

Per altra banda, és important tenir en compte que si dins de l’interval de cerca [a, b] hi ha d’haver-hi un zero, això voldrà dir que si f(a)>0 llavors f(b)<0 o de manera inversa si f(a) és negatiu, f(b) haurà de ser positiu. Gràficament, per a que hi hagi un punt on la funció creui l’eix X, hi ha d’haver-hi un punt de la funció per sobre de l’eix X en un costat, i un punt de la funció per sota de l’eix a l’altre costat. Penseu-hi! En realitat aquesta idea que pot semblar trivial, però que a vegades oblidem tenir en compte, és precisament el que enuncia el Teorema de Bolzano.

Sigui f:[a,b] ? R contínua tal que f(a)*f(b) < 0. Llavors, f té un zero a (a,b), és a dir, existeix x0 E (a,b) tal que f(x0) = 0.

I és el que aplicarem al principi de qualsevol aplicació del Mètode de Newton per definir l’interval de cerca [a,b] on es troba X*.

Si tornem a la funció que teníeu de “deures” del vídeo anterior, jo us vaig dir que agaféssiu X0=2, però per què? La funció era f(x)= x^3-2x-5. Si no us hagués donat X0, n’hauríeu d’haver triat una vosaltres, i si apliquem Bolzano veiem que:

f(0)<0, f(1)<0, f(2)<0, i f(3)>0 Com que entre x=2 i x=3 hi ha un canvi de signe de la funció, podem dir que [2,3] serà el nostre interval de cerca. Té sentit agafar X0=2, però també podríem haver agafat qualsevol altre valor entre 2 i 3.

Ara suposem que es vol aproximar un zero de f(x)=6x^3 -2x^2 – 2x-1. El primer que fem es buscar l’interval de cerca aplicant Bolzano com abans.

f(0)<0, i f(1)>1 per tant podríem dir que X* E [0,1]. En aquest cas si agafem X0=0,5 (recordeu que, si l’interval està ben definit, x0 pot ser qualsevol valor dins d’aquest interval) i calculem X1

X1= 0,5 – f(0,5)/f’(0,5) = 4

En aquest cas, X1 ens queda fora de l’interval de cerca i per tant vol dir que alguna cosa no va bé. De fet, f(4)= 343, i per tant està molt allunyat de 0. Aquest exemple posa de manifest que aplicant només el Teorema de Bolzano pot ser que l’interval de cerca que ens definim no sigui suficientment petit com per garantir que el Mètode de Newton convergeixi en tot ell. Per a que això sigui cert s’ha de satisfer el següent:

Siguin [a,b] un interval de cerca d’x* (típicament un interval per al qual f(a)*f(b)<0) i f:[a,b] ? R una funció derivable dues vegades tal que f’(x)!= 0 per a tot x E [a,b]. Si

|x*-x0| < 2/max |f’’(x)/f’x)| llavors lim k->inf Xk = x*

Aquesta fórmula es pot deduir a partir del residu de Lagrange, però com que aquest curs no s’ha explicat a classe, aquells que tingueu interès podreu trobar d’on surt als apunts que teniu penjats al Moodle.

Anem a veure com aplicaríem aquesta fórmula a l’exemple d’abans que ens havia donat problemes. Per començar mirarem si hi ha algun punt en [0,1] que faci que la f’(x)=0.

F’(x)=18x^2- 4x-2 =0 si resolem l’equació de segon grau tindrem que f’(0,46) = 0 Per tant hem de definir un nou interval de cerca que no inclogui aquest punt.

Recordem que f(1)=1 i f(0)=-1, si fem x=0,5 tenim que f(0,5)=-1,75 <0 Per tant el nostre nou interval podria ser [0,5 , 1]. Si apliquem la fórmula de la Condició de Convergència, tenim que

|X*-x0| < 2/f’’(1)/f’(0,5) Com que f’ i f’’ són monòtones creixents, el valor que maximitza la segona derivada és l’extrem superior de l’interval, i el valor que minimitza la primera derivada és l’extrem inferior de l’interval. Per tant f’(x)= 18x^2-4x-2 i f’(0,5)= 0,5 i f’’(x)= 36x-4 i f’’(1)=32

Ens queda que l’interval |x*-x0|< 0,03125 per garantir la convergència del mètode. Com que el nostre interval és [0,5 , 1] es pot veure fàcilment que no es compleix la condició, i que per tant podria ser que si agaféssim x0=0,5 ens tornessin a donar valors fora de l’interval. Això podria ser degut a que 0,5 és massa proper a x=0,46, on la derivada s’anul·lava.

Intentem ajustar millor l’interval. Si agafem x=0,75, f(0,75) = -1,09 <0 segueix sent menor que zero i per tant un possible interval seria [0,75, 1]. En aquest cas si apliqueu la Condició de convergència veureu que si que és compleix.

Recapitulant, en aquest vídeo hem vist els tres criteris d’aturada més rellevants, i hem analitzat com es tria el valor de x0 adequadament aplicant el Teorema de Bolzano i la fórmula de la Condició de Convergència. En el proper vídeo veurem altres aplicacions del Mètode de Newton que estem segurs us resultaran interessants i sorprenents.

Abans de visualitzar el darrer dels tres vídeos que us hem preparat, us demanem que feu els següents exercicis:

1. Realitzeu els càlculs que confirmen que [0,75,1] és un interval de cerca que garanteix la convergència del Mètode de Newton per a la funció f(x)= 6x^3-2x^2-2x-1 i trieu un possible valor de X0.

2. Trobeu un interval de cerca que garanteixi la convergència del Mètode de Newton per a la funció f(x)=x^3-2x-5.

3. Enumereu els tres criteris d’aturada que hem explicat i expliqueu-los amb les vostres paraules.

4. Volem utilitzar el Mètode de Newton per a resoldre l’arrel quadrada d’un nombre (que no sigui trivial). Com plantejaríeu l’equació general? I en cas que aquest nombre fos pi, sabríeu triar un x0 adequat?