4 5 decimal

&[DATE] &[TIME] - &[FILENAME]

Broyden’s methods with direct or inverse update

REFERENCES http://www-users.cs.umn.edu/~saad/PDF/umsi-2007-100.pdf -- PAGE 5

Broyden's method - solving nonlinear system of equations,
INVERSE UPDATE (with Sherman-Morrison formula)
Arguments:
f(1) - vector function returning vector of size n (f(x)≡0)
x0  - initial estimates, vector of size n
ε - tolerance (small number)
maxiter - naximal number of iterations (if exceeded - method not converging) 1 f x.init ε maxiter Broyden.ref3 iter 0 : x x.init : f0 x f : B x length identity : iter maxiter < Δx B x f * - stack eval : Δx min abs ε 2^< (Δx max abs ε 2^< (& break x x Δx + eval : f1 x f : Δf f1 f0 - : B B Δx B Δf * - (Δx transpose B * Δx transpose B * Δf * (1 el Δx transpose B * Δf * (1 el 0 ≡ (ε 2^* + / * + eval : f0 f1 : iter iter 1 + : 61 line if 21 line while konv iter maxiter ≥ x not converging 21 mat x iter 21 mat if : 61 line :

Broyden's method - solving nonlinear system of equations,
INVERSE UPDATE (with Sherman-Morrison formula)
Arguments:
f(1) - vector function returning vector of size n (f(x)≡0)
x0  - initial estimates, vector of size n
ε - tolerance (small number)
maxiter - naximal number of iterations (if exceeded - method not converging) 1 f x.init ε maxiter Broyden.ref3 iter 0 : x x.init : f0 x f : B x length identity : Δf 111 mat : iter maxiter < Δx B x f * - stack eval : Δf min abs ε < (Δf max abs ε < (& break x x Δx + eval : f1 x f : Δf f1 f0 - : B B Δx B Δf * - (Δx transpose B * Δx transpose B * Δf * (1 el Δx transpose B * Δf * (1 el 0 ≡ (ε 2^* + / * + eval : f0 f1 : iter iter 1 + : 61 line if 21 line while konv iter maxiter ≥ x not converging 21 mat x iter 21 mat if : 71 line :

update methods B Δx B Δf * - (# Δf transpose Δf transpose Δf * (1 el / bad update (bad is not wrong) 21 line Δx transpose B * Δx transpose B * Δf * (1 el / good update 21 line if * +

x length identity

ε 2^

algoritm homemade hack

bad broyden method B B Δx B Δf * - (Δf transpose Δf transpose Δf * (1 el Δf transpose Δf * (1 el 0 ≡ (ε 2^* + / * + eval :

good broyden method B B Δx B Δf * - (Δx transpose B * Δx transpose B * Δf * (1 el Δx transpose B * Δf * (1 el 0 ≡ (ε 2^* + / * + eval :

x f x 1 el x 2 el x 3 el x 4 el x 5 el x 6 el 61 mat Jacob

Checking :

x f X1 x 1 el 2 x 2 el * - 5 + 11 mat : X2 x 1 el 3 x 2 el * + 1 - 11 mat : X1 X2 stack 31 line :

x0 1221 mat :

x0 f 2621 mat

eps 105 -^:

Accuracy:

maxiter 100 :

Max. number of iterations

Calling broyden:

res.ref X# f x0 eps maxiter Broyden.ref3 :

res.ref 2.6 - 1.2 21 mat 521 mat

res.ref 1 el f 0021 mat

#X1 f x0 eps maxiter 1 Broyden 2.6 - 1.2 21 mat 511 mat 21 mat

Good!

F1 1 :

F2 1.2 0.5 * 0.21 / F1 * :

F2 2.8571

A 10101040222012112000000246 mat :

n1 10000061 mat :

n2 0 0.21 F2 * 000 0.79 F2 * 61 mat :

n2 0 0.6 000 2.2571 61 mat

n30 n1 n2 + :

n3 f1 AB A n3 n1 - n2 - (* : K n1 1 el n3 1 el - n1 1 el / 0.32 - 11 mat : S n3 3 el 9 n3 5 el * - 11 mat : AB K S stack 41 line :

n30 f1 0000 0.32 - 061 mat

n30 1 0.6 000 2.26 61 mat

eps 1010 -^:

Accuracy:

maxiter 100 :

Max. number of iterations

0.68 0.424 0.288 0.32 0.032 2.2571 61 mat f1 000 8.5714 105 -^* - 0061 mat

Calling broyden:

res X# f1 n30 eps maxiter Broyden :

res.ref X# f1 n30 eps maxiter Broyden.ref3 :

res.ref 1 el f1 0 4.7664 1016 -^* 5.7115 1016 -^* 1.1429 1014 -^* 1.2 1015 -^* 81016 -^* 61 mat

res.ref 0.68 0.42 0.29 0.32 0.03 2.26 61 mat 2421 mat

#X2 f1 n30 eps maxiter 1 Broyden 0.68 0.42 0.29 0.32 0.03 2.26 61 mat 2111 mat 21 mat

#X2 f1 n30 eps maxiter 1 Broyden 1 el f1 0 2.6 1015 -^* - 6.4 1016 -^* - 00061 mat

Good!

61

x 2^1 eps maxiter Broyden 0

Good!

x 1 + (2^0 eps maxiter Broyden 1 -

Good!

x 1 el 2 x 2 el * - 5 + x 1 el 3 x 2 el * + 1 - 21 sys 1221 sys eps maxiter Broyden 2.6 - 1.2 21 mat

Good!

x 1 el 3 + (x 2 el 3^7 - (* 18 + x 2 el e x 1 el^* 1 - sin 21 mat 0.5 - 1.4 21 mat eps maxiter Broyden 6.57 1016 -^* - 121 mat

x 1 el 3 + (x 2 el 3^7 - (* 18 + x 2 el e x 1 el^* 1 - sin 21 sys 0.5 - 1.4 21 sys eps maxiter Broyden 6.57 1016 -^* - 121 mat

x f x 1 el 3 + (x 2 el 3^7 - (* 18 + x 2 el e x 1 el^* 1 - sin 21 mat :

x J x f x 1 el x 2 el 21 mat Jacob :

x# f 183 x# 1 el + (7 - x# 2 el 3^+ (* + 1 - x# 2 el e x# 1 el^* + sin 21 mat

x0 0.5 - 1.4 21 mat :

x0 f 7.36 0.1503 - 21 mat

x# f x0 eps maxiter 1 Broyden 6.6 1016 -^* - 121 mat 4711 mat 21 mat

0121 mat f 0021 mat

res x# f x0 eps maxiter Broyden.ref3 :

res 0.68 0.424 0.288 0.32 0.032 2.2571 61 mat

x1 x0 x0 J 1 -^x0 f * - :

x1 f 0.5869 0.0273 - 21 mat

x0 x1 :

<-Newton Rapson

x1 x0 x0 J 1 -^x0 f * - :

x1 f 0.0023 1.7041 105 -^* 21 mat

x0 x1 :

<-Converging in few iterations

x1 x0 x0 J 1 -^x0 f * - :

x1 f 1.5671 107 -^* 1.2239 108 -^* - 21 mat

x0 x1 :

x1 x0 x0 J 1 -^x0 f * - :

x1 f 2.0525 1014 -^* 8.1933 1016 -^* 21 mat

x0 x1 :

x1 3.20632898644912 1015 -^* - 121 mat

x# f x# 1 el x# 2 el 21 mat x0 roots 1.36341497322497 1016 -^* - 121 mat

x1 f 2.05249825033801 1014 -^* 8.19334197429104 1016 -^* 21 mat

x1 J 6 - 91122 mat