74. The Richardson Iteration#
also called simple iteration is the fixed point iteration
\[
x^{k+1} := x^k + \alpha \, (b - A x^k)
\]
with an arbitrary starting value \(x^0 \in {\mathbb R}^n\), and a properly cosen damping parameter \(\alpha\). The misfit of the equation, \(r = b - A x^k\) is called residual.
The solution \(x^\ast\) is a fixed point of the iteration (since \(b - A x^\ast = 0\)).
If we define the error as
\[
e^k = x^k - x^\ast,
\]
the error propagation from one step to the next is
\[\begin{align*}
e^{k+1} & = x^{k+1} - x^\ast = x^k + \alpha (b - A x^k) - x^\ast \\
& = x^k - x^\ast + \alpha A (x^\ast - x^k) = (I - \alpha A) (x^k - x^\ast)
\end{align*}\]
This means the new error is obtained from the old error by the error propagation matrix
\[
e^{k+1} = \underbrace{(I - \alpha A)}_{M} \, e^k
\]
Two strategies to verify convergence are:
prove that the spectral radius
\[
\rho(I - \alpha A) := \max_{\lambda \in \sigma(I - \alpha A)} |\lambda| < 1
\]
find some norm \(\| \cdot \|\) such that the matrix norm (=operator norm)
\[
\| I - \alpha A \| := \sup_{x \in {\mathbb R}^n} \frac{ \| (I - \alpha A) x \| }{ \| x \| } < 1
\]
The first one, \(\rho < 1\), only provides asymptotic convergence. This is easily proven if A is diagonizable, i.e. it features a full set of eigenvectors \(z^j\) and eigenvalues \(\lambda_j\). Expand the initial error as
\[
e^0 = \sum_j e^0_j z^j,
\]
then
\[
e^k = \sum_j (1-\alpha \lambda_j)^k e^0_j z^j
\]
and
\[
\| e^k \| \leq \rho^k \sum_j | e^0_j | \| z^j \|
\]
This means \(\| e^k \| \leq C \rho^k\), but the error does not have to decrease monotonically.
However, if \(\| I - \alpha A \| < 1\), then
\[
\| e^{k+1} \| \leq \| I - \alpha A \| \, \| e^k \|,
\]
proves that the error decreases in every iteration step. Note that the matrix norm is the operator norm generated by the vector norm.
Some facts:
If the norm \(\| \cdot \|\) is generated by an inner product \(\left< \cdot, \cdot \right>\) (parallelogram identity), and \(M\) is some self adjoint matrix with respect to this inner product, i.e.
\[ \left< M x, y \right> = \left< x, M y \right>, \]then \(\rho(M) = \| M \|\)
If \(\left< \cdot , \cdot \right>\) is the Euklidean inner product, then \(M\) is self-adjoint exactly when \(M\) is symmetric.
The spectral radius is bounded by every operator norm. There exists some norm such that the operator norm is arbitrary close to the spectral radius, i.e.
\[ \rho(M) = \inf_{ \text{norms} \| \cdot \| } \| M \| \]
74.1. Optimizing the relaxation parameter \(\alpha\)#
Let \(A\) be SPD, and let \(\sigma(A) = \{ \lambda_i \in {\mathbb R} \}\) with \(0 < \lambda_1 \leq \lambda_2 \ldots \leq \lambda_n\).
Then the eigenvalues of the error propagation matrix \(M = I - \alpha A\) are \(\{ 1 - \alpha \lambda_i \}\).
Whenever we choose
\[
0 < \alpha < \frac{2}{\lambda_n}
\]
we obtain \(\rho(M) < 1\), and a convergent iteration.
The spectral radius of \(M\) is
\[
\rho(M) = \max_i \{ | 1 - \alpha \lambda_i| \} =
\max \{ 1 - \alpha \lambda_1, - (1-\alpha \lambda_n) \}
\]
The maximum is minimized if we choose \(\alpha\) optimally such that
\[
1 - \alpha \lambda_1 = - (1 - \alpha \lambda_n),
\]
i.e.
\[
\alpha_{\text{opt}} = \frac{2}{\lambda_1 + \lambda_n}
\]
leading to the optimal rate of convergence
\[
\rho_{\text{opt}} = \frac{\lambda_n - \lambda_1}{\lambda_n+\lambda_1}
\approx 1 - 2 \frac{\lambda_1}{\lambda_n} = 1 - \frac{2}{\kappa(A)}
\]
with the condition number \(\kappa(A) = \lambda_n(A) / \lambda_1(A)\).
After \(N\) iterations, the error is reduced by
\[
\left(1 - \frac{1}{\kappa}\right)^N.
\]
To obtain an error reduction by by a factor of \(\varepsilon\) one needs
\[
N = \frac{\log \varepsilon}{\log (1-1/\kappa)} \approx \kappa \, | \log \varepsilon |
\]
74.2. Experiments with the Richardson iteration#
from ngsolve import *
mesh = Mesh(unit_square.GenerateMesh(maxh=0.1))
fes = H1(mesh, order=1)
u,v = fes.TnT()
a = BilinearForm(grad(u)*grad(v)*dx+10*u*v*dx).Assemble()
f = LinearForm(x*y*v*dx).Assemble()
gfu = GridFunction(fes)
we determine (an approximation to) the largest eigenvalue by a few steps of the power iteration:
hv = gfu.vec.CreateVector()
hv2 = gfu.vec.CreateVector()
hv.SetRandom()
hv.data /= Norm(hv)
for k in range(20):
hv2.data = a.mat * hv
rho = Norm(hv2)
print (rho)
hv.data = 1/rho * hv2
1.6888766633030172
4.424719775134565
4.755803881591664
4.924455630566479
5.033550134956875
5.110795841634
5.167742675863414
5.210802655494004
5.244053974802499
5.270222947337114
5.291170272316779
5.308186021433597
5.3221807509626915
5.333810564616628
5.3435587882737945
5.351789339460098
5.358781839686268
5.3647550198472125
5.369882607946284
5.374304348881506
Run the Richardson iteration:
alpha = 1 / rho
r = f.vec.CreateVector()
gfu.vec[:] = 0
err0 = Norm(f.vec)
its = 0
errhist = []
while True:
r.data = f.vec - a.mat * gfu.vec
err = Norm(r)
print ("iteration", its, "res=", err)
errhist.append (err)
gfu.vec.data += alpha * r
if err < 1e-8 * err0 or its > 10000: break
its = its+1
print ("needed", its, "iterations")
iteration 0 res= 0.02953105456408729
iteration 1 res= 0.02823937043904577
iteration 2 res= 0.02739923820989957
iteration 3 res= 0.02671285209043731
iteration 4 res= 0.026106165845752975
iteration 5 res= 0.025547660393190508
iteration 6 res= 0.02502190229848544
iteration 7 res= 0.024520650010776822
iteration 8 res= 0.024039151252160666
iteration 9 res= 0.023574456931040183
iteration 10 res= 0.023124605010135395
iteration 11 res= 0.022688204217791667
iteration 12 res= 0.02226421107397248
iteration 13 res= 0.021851804767669264
iteration 14 res= 0.02145031376678788
iteration 15 res= 0.021059170941088272
iteration 16 res= 0.02067788503628397
iteration 17 res= 0.020306021882211762
iteration 18 res= 0.019943191601515753
iteration 19 res= 0.01958903963845144
iteration 20 res= 0.01924324029266319
iteration 21 res= 0.01890549194051192
iteration 22 res= 0.018575513421630926
iteration 23 res= 0.018253041248376206
iteration 24 res= 0.017937827408539456
iteration 25 res= 0.017629637603994545
iteration 26 res= 0.01732824981537908
iteration 27 res= 0.017033453114668834
iteration 28 res= 0.016745046669165237
iteration 29 res= 0.016462838895448296
iteration 30 res= 0.016186646732443136
iteration 31 res= 0.015916295010325897
iteration 32 res= 0.01565161589748745
iteration 33 res= 0.015392448411804479
iteration 34 res= 0.015138637985461521
iteration 35 res= 0.01489003607481596
iteration 36 res= 0.014646499808505102
iteration 37 res= 0.014407891668303209
iteration 38 res= 0.014174079198250781
iteration 39 res= 0.013944934738371122
iteration 40 res= 0.013720335179915352
iteration 41 res= 0.013500161739575689
iteration 42 res= 0.013284299750507331
iteration 43 res= 0.013072638468324084
iteration 44 res= 0.012865070890497852
iteration 45 res= 0.012661493587810638
iteration 46 res= 0.012461806546688563
iteration 47 res= 0.0122659130213987
iteration 48 res= 0.012073719395216755
iteration 49 res= 0.011885135049780952
iteration 50 res= 0.011700072241939408
iteration 51 res= 0.011518445987476231
iteration 52 res= 0.01134017395116936
iteration 53 res= 0.011165176342691268
iteration 54 res= 0.010993375817914377
iteration 55 res= 0.010824697385226926
iteration 56 res= 0.010659068316504325
iteration 57 res= 0.010496418062414086
iteration 58 res= 0.010336678171763373
iteration 59 res= 0.010179782214623883
iteration 60 res= 0.010025665708992965
iteration 61 res= 0.009874266050770318
iteration 62 res= 0.009725522446848581
iteration 63 res= 0.0095793758511328
iteration 64 res= 0.0094357689033186
iteration 65 res= 0.009294645870272492
iteration 66 res= 0.009155952589869842
iteration 67 res= 0.009019636417156822
iteration 68 res= 0.008885646172712864
iteration 69 res= 0.008753932093098625
iteration 70 res= 0.008624445783283126
iteration 71 res= 0.008497140170950655
iteration 72 res= 0.008371969462595039
iteration 73 res= 0.008248889101314771
iteration 74 res= 0.00812785572622858
iteration 75 res= 0.008008827133435254
iteration 76 res= 0.007891762238447302
iteration 77 res= 0.007776621040031491
iteration 78 res= 0.007663364585393684
iteration 79 res= 0.007551954936648961
iteration 80 res= 0.007442355138521397
iteration 81 res= 0.007334529187220788
iteration 82 res= 0.007228442000446892
iteration 83 res= 0.007124059388473963
iteration 84 res= 0.007021348026271039
iteration 85 res= 0.006920275426615951
iteration 86 res= 0.006820809914162701
iteration 87 res= 0.006722920600424102
iteration 88 res= 0.006626577359633681
iteration 89 res= 0.006531750805451959
iteration 90 res= 0.006438412268484419
iteration 91 res= 0.006346533774579859
iteration 92 res= 0.006256088023878927
iteration 93 res= 0.0061670483705844785
iteration 94 res= 0.006079388803426346
iteration 95 res= 0.0059930839267943
iteration 96 res= 0.005908108942514389
iteration 97 res= 0.005824439632244463
iteration 98 res= 0.005742052340466134
iteration 99 res= 0.005660923958051125
iteration 100 res= 0.005581031906380862
iteration 101 res= 0.005502354121999212
iteration 102 res= 0.00542486904177874
iteration 103 res= 0.005348555588582202
iteration 104 res= 0.005273393157400904
iteration 105 res= 0.005199361601953211
iteration 106 res= 0.0051264412217262596
iteration 107 res= 0.005054612749445358
iteration 108 res= 0.004983857338955445
iteration 109 res= 0.004914156553500155
iteration 110 res= 0.004845492354384357
iteration 111 res= 0.004777847090006343
iteration 112 res= 0.004711203485246829
iteration 113 res= 0.0046455446312019455
iteration 114 res= 0.004580853975248373
iteration 115 res= 0.00451711531142856
iteration 116 res= 0.004454312771145126
iteration 117 res= 0.004392430814153372
iteration 118 res= 0.004331454219841595
iteration 119 res= 0.004271368078789117
iteration 120 res= 0.004212157784592291
iteration 121 res= 0.004153809025949214
iteration 122 res= 0.004096307778994073
iteration 123 res= 0.004039640299872599
iteration 124 res= 0.003983793117550147
iteration 125 res= 0.003928753026844292
iteration 126 res= 0.0038745070816743644
iteration 127 res= 0.003821042588520357
iteration 128 res= 0.003768347100083895
iteration 129 res= 0.0037164084091444657
iteration 130 res= 0.0036652145426040762
iteration 131 res= 0.003614753755714056
iteration 132 res= 0.0035650145264774957
iteration 133 res= 0.0035159855502215516
iteration 134 res= 0.003467655734333764
iteration 135 res= 0.0034200141931567526
iteration 136 res= 0.003373050243035838
iteration 137 res= 0.0033267533975147034
iteration 138 res= 0.0032811133626736272
iteration 139 res= 0.00323612003260588
iteration 140 res= 0.0031917634850273076
iteration 141 res= 0.0031480339770148906
iteration 142 res= 0.0031049219408696275
iteration 143 res= 0.003062417980099956
iteration 144 res= 0.00302051286552124
iteration 145 res= 0.002979197531467795
iteration 146 res= 0.002938463072113574
iteration 147 res= 0.0028983007378978014
iteration 148 res= 0.002858701932052295
iteration 149 res= 0.002819658207226821
iteration 150 res= 0.0027811612622094836
iteration 151 res= 0.002743202938738966
iteration 152 res= 0.0027057752184054622
iteration 153 res= 0.002668870219637576
iteration 154 res= 0.0026324801947722578
iteration 155 res= 0.0025965975272050643
iteration 156 res= 0.00256121472861831
iteration 157 res= 0.0025263244362842122
iteration 158 res= 0.002491919410441126
iteration 159 res= 0.002457992531739877
iteration 160 res= 0.002424536798758595
iteration 161 res= 0.0023915453255833356
iteration 162 res= 0.0023590113394526407
iteration 163 res= 0.0023269281784639704
iteration 164 res= 0.0022952892893399915
iteration 165 res= 0.0022640882252528503
iteration 166 res= 0.0022333186437046098
iteration 167 res= 0.0022029743044621043
iteration 168 res= 0.002173049067544407
iteration 169 res= 0.0021435368912614433
iteration 170 res= 0.0021144318303019344
iteration 171 res= 0.002085728033869393
iteration 172 res= 0.002057419743864472
iteration 173 res= 0.002029501293112352
iteration 174 res= 0.002001967103633752
iteration 175 res= 0.001974811684958296
iteration 176 res= 0.0019480296324787775
iteration 177 res= 0.0019216156258453699
iteration 178 res= 0.0018955644273982008
iteration 179 res= 0.0018698708806376104
iteration 180 res= 0.0018445299087304341
iteration 181 res= 0.0018195365130516431
iteration 182 res= 0.0017948857717602338
iteration 183 res= 0.0017705728384081081
iteration 184 res= 0.0017465929405812732
iteration 185 res= 0.001722941378572271
iteration 186 res= 0.001699613524082881
iteration 187 res= 0.0016766048189564245
iteration 188 res= 0.0016539107739385332
iteration 189 res= 0.0016315269674658324
iteration 190 res= 0.0016094490444815198
iteration 191 res= 0.0015876727152773122
iteration 192 res= 0.001566193754360729
iteration 193 res= 0.0015450079993473281
iteration 194 res= 0.0015241113498768114
iteration 195 res= 0.0015034997665527453
iteration 196 res= 0.0014831692699049962
iteration 197 res= 0.0014631159393741534
iteration 198 res= 0.0014433359123177253
iteration 199 res= 0.0014238253830371284
iteration 200 res= 0.0014045806018250367
iteration 201 res= 0.0013855978740326983
iteration 202 res= 0.001366873559156419
iteration 203 res= 0.0013484040699428739
iteration 204 res= 0.0013301858715127888
iteration 205 res= 0.001312215480502192
iteration 206 res= 0.001294489464221375
iteration 207 res= 0.0012770044398303666
iteration 208 res= 0.0012597570735310582
iteration 209 res= 0.0012427440797754064
iteration 210 res= 0.0012259622204890562
iteration 211 res= 0.001209408304310367
iteration 212 res= 0.001193079185844177
iteration 213 res= 0.0011769717649300594
iteration 214 res= 0.0011610829859246702
iteration 215 res= 0.0011454098369979085
iteration 216 res= 0.0011299493494423454
iteration 217 res= 0.0011146985969959018
iteration 218 res= 0.0010996546951771817
iteration 219 res= 0.0010848148006333037
iteration 220 res= 0.0010701761104998765
iteration 221 res= 0.001055735861772813
iteration 222 res= 0.0010414913306918386
iteration 223 res= 0.0010274398321351017
iteration 224 res= 0.001013578719025082
iteration 225 res= 0.0009999053817450105
iteration 226 res= 0.0009864172475660736
iteration 227 res= 0.0009731117800847485
iteration 228 res= 0.0009599864786702967
iteration 229 res= 0.0009470388779219465
iteration 230 res= 0.0009342665471358661
iteration 231 res= 0.0009216670897813596
iteration 232 res= 0.0009092381429863723
iteration 233 res= 0.0008969773770318476
iteration 234 res= 0.0008848824948549753
iteration 235 res= 0.0008729512315609884
iteration 236 res= 0.0008611813539432494
iteration 237 res= 0.0008495706600118149
iteration 238 res= 0.0008381169785297069
iteration 239 res= 0.0008268181685573331
iteration 240 res= 0.0008156721190044844
iteration 241 res= 0.000804676748189794
iteration 242 res= 0.000793830003407778
iteration 243 res= 0.0007831298605029616
iteration 244 res= 0.0007725743234510354
iteration 245 res= 0.0007621614239470998
iteration 246 res= 0.0007518892210006033
iteration 247 res= 0.0007417558005369036
iteration 248 res= 0.0007317592750053966
iteration 249 res= 0.0007218977829940334
iteration 250 res= 0.0007121694888500846
iteration 251 res= 0.0007025725823070059
iteration 252 res= 0.0006931052781173365
iteration 253 res= 0.000683765815691529
iteration 254 res= 0.0006745524587424851
iteration 255 res= 0.0006654634949358326
iteration 256 res= 0.0006564972355456775
iteration 257 res= 0.0006476520151158763
iteration 258 res= 0.0006389261911266544
iteration 259 res= 0.0006303181436663829
iteration 260 res= 0.0006218262751086284
iteration 261 res= 0.0006134490097941009
iteration 262 res= 0.0006051847937177537
iteration 263 res= 0.0005970320942205065
iteration 264 res= 0.0005889893996859956
iteration 265 res= 0.0005810552192417345
iteration 266 res= 0.0005732280824651742
iteration 267 res= 0.0005655065390939968
iteration 268 res= 0.0005578891587410586
iteration 269 res= 0.0005503745306135565
iteration 270 res= 0.0005429612632365182
iteration 271 res= 0.0005356479841804902
iteration 272 res= 0.0005284333397933885
iteration 273 res= 0.0005213159949362896
iteration 274 res= 0.0005142946327233561
iteration 275 res= 0.0005073679542655416
iteration 276 res= 0.0005005346784182119
iteration 277 res= 0.0004937935415325097
iteration 278 res= 0.00048714329721051227
iteration 279 res= 0.0004805827160638705
iteration 280 res= 0.0004741105854762021
iteration 281 res= 0.00046772570936895116
iteration 282 res= 0.000461426907970715
iteration 283 res= 0.0004552130175898656
iteration 284 res= 0.0004490828903907686
iteration 285 res= 0.0004430353941730894
iteration 286 res= 0.00043706941215439964
iteration 287 res= 0.0004311838427559571
iteration 288 res= 0.0004253775993916927
iteration 289 res= 0.0004196496102601543
iteration 290 res= 0.000413998818139616
iteration 291 res= 0.00040842418018602865
iteration 292 res= 0.0004029246677340105
iteration 293 res= 0.0003974992661007331
iteration 294 res= 0.00039214697439252024
iteration 295 res= 0.00038686680531436004
iteration 296 res= 0.00038165778498214795
iteration 297 res= 0.0003765189527375717
iteration 298 res= 0.00037144936096575337
iteration 299 res= 0.0003664480749153657
iteration 300 res= 0.0003615141725215587
iteration 301 res= 0.00035664674423113745
iteration 302 res= 0.00035184489283045895
iteration 303 res= 0.000347107733275717
iteration 304 res= 0.0003424343925256563
iteration 305 res= 0.0003378240093765561
iteration 306 res= 0.000333275734299761
iteration 307 res= 0.0003287887292814066
iteration 308 res= 0.0003243621676643722
iteration 309 res= 0.00031999523399256984
iteration 310 res= 0.0003156871238574116
iteration 311 res= 0.00031143704374641385
iteration 312 res= 0.000307244210893929
iteration 313 res= 0.0003031078531341059
iteration 314 res= 0.00029902720875570033
iteration 315 res= 0.00029500152635916467
iteration 316 res= 0.0002910300647155816
iteration 317 res= 0.00028711209262769334
iteration 318 res= 0.00028324688879274916
iteration 319 res= 0.0002794337416674011
iteration 320 res= 0.0002756719493344232
iteration 321 res= 0.0002719608193713852
iteration 322 res= 0.0002682996687209384
iteration 323 res= 0.0002646878235632389
iteration 324 res= 0.0002611246191898538
iteration 325 res= 0.00025760939987962546
iteration 326 res= 0.00025414151877614763
iteration 327 res= 0.000250720337767003
iteration 328 res= 0.00024734522736469445
iteration 329 res= 0.0002440155665891799
iteration 330 res= 0.0002407307428520316
iteration 331 res= 0.00023749015184231122
iteration 332 res= 0.00023429319741391142
iteration 333 res= 0.0002311392914744657
iteration 334 res= 0.0002280278538758976
iteration 335 res= 0.00022495831230637337
iteration 336 res= 0.00022193010218378664
iteration 337 res= 0.00021894266655078556
iteration 338 res= 0.0002159954559710811
iteration 339 res= 0.0002130879284273987
iteration 340 res= 0.00021021954922067403
iteration 341 res= 0.00020738979087067433
iteration 342 res= 0.00020459813301810064
iteration 343 res= 0.00020184406232785004
iteration 344 res= 0.0001991270723937537
iteration 345 res= 0.00019644666364460492
iteration 346 res= 0.00019380234325139733
iteration 347 res= 0.00019119362503593974
iteration 348 res= 0.0001886200293806798
iteration 349 res= 0.0001860810831397209
iteration 350 res= 0.0001835763195511649
iteration 351 res= 0.00018110527815060298
iteration 352 res= 0.0001786675046857363
iteration 353 res= 0.0001762625510322531
iteration 354 res= 0.00017388997511084546
iteration 355 res= 0.0001715493408052901
iteration 356 res= 0.00016924021788175308
iteration 357 res= 0.00016696218190914404
iteration 358 res= 0.0001647148141805264
iteration 359 res= 0.00016249770163567783
iteration 360 res= 0.00016031043678467537
iteration 361 res= 0.00015815261763245966
iteration 362 res= 0.00015602384760458326
iteration 363 res= 0.0001539237354738029
iteration 364 res= 0.00015185189528781344
iteration 365 res= 0.000149807946297833
iteration 366 res= 0.00014779151288830765
iteration 367 res= 0.00014580222450745925
iteration 368 res= 0.0001438397155988288
iteration 369 res= 0.00014190362553376357
iteration 370 res= 0.00013999359854476522
iteration 371 res= 0.00013810928365984835
iteration 372 res= 0.0001362503346376656
iteration 373 res= 0.00013441640990363956
iteration 374 res= 0.00013260717248685992
iteration 375 res= 0.00013082228995791898
iteration 376 res= 0.00012906143436751697
iteration 377 res= 0.00012732428218602477
iteration 378 res= 0.00012561051424368565
iteration 379 res= 0.00012391981567177213
iteration 380 res= 0.00012225187584458122
iteration 381 res= 0.00012060638832196626
iteration 382 res= 0.00011898305079298959
iteration 383 res= 0.00011738156502008971
iteration 384 res= 0.00011580163678410221
iteration 385 res= 0.0001142429758299726
iteration 386 res= 0.00011270529581331979
iteration 387 res= 0.00011118831424765834
iteration 388 res= 0.00010969175245219168
iteration 389 res= 0.00010821533550064501
iteration 390 res= 0.00010675879217042309
iteration 391 res= 0.00010532185489277303
iteration 392 res= 0.00010390425970337438
iteration 393 res= 0.0001025057461937968
iteration 394 res= 0.00010112605746342797
iteration 395 res= 9.97649400722374e-05
iteration 396 res= 9.84221439940524e-05
iteration 397 res= 9.709742257051636e-05
iteration 398 res= 9.579053246564478e-05
iteration 399 res= 9.45012336210429e-05
iteration 400 res= 9.322928921168216e-05
iteration 401 res= 9.197446560227631e-05
iteration 402 res= 9.073653230430786e-05
iteration 403 res= 8.951526193354782e-05
iteration 404 res= 8.831043016824013e-05
iteration 405 res= 8.71218157077705e-05
iteration 406 res= 8.594920023192106e-05
iteration 407 res= 8.479236836076931e-05
iteration 408 res= 8.3651107614936e-05
iteration 409 res= 8.252520837654474e-05
iteration 410 res= 8.141446385062537e-05
iteration 411 res= 8.031867002707837e-05
iteration 412 res= 7.923762564313524e-05
iteration 413 res= 7.817113214625688e-05
iteration 414 res= 7.711899365772136e-05
iteration 415 res= 7.608101693648057e-05
iteration 416 res= 7.505701134367621e-05
iteration 417 res= 7.404678880751921e-05
iteration 418 res= 7.305016378870288e-05
iteration 419 res= 7.206695324632564e-05
iteration 420 res= 7.109697660416452e-05
iteration 421 res= 7.014005571743863e-05
iteration 422 res= 6.919601484012095e-05
iteration 423 res= 6.826468059258665e-05
iteration 424 res= 6.734588192967385e-05
iteration 425 res= 6.643945010930179e-05
iteration 426 res= 6.554521866137629e-05
iteration 427 res= 6.466302335727477e-05
iteration 428 res= 6.379270217946547e-05
iteration 429 res= 6.293409529194177e-05
iteration 430 res= 6.208704501066366e-05
iteration 431 res= 6.12513957746227e-05
iteration 432 res= 6.042699411725494e-05
iteration 433 res= 5.961368863822055e-05
iteration 434 res= 5.881132997550636e-05
iteration 435 res= 5.8019770778078605e-05
iteration 436 res= 5.7238865678715143e-05
iteration 437 res= 5.646847126727258e-05
iteration 438 res= 5.570844606439404e-05
iteration 439 res= 5.4958650495429885e-05
iteration 440 res= 5.4218946864813676e-05
iteration 441 res= 5.348919933076741e-05
iteration 442 res= 5.276927388030236e-05
iteration 443 res= 5.20590383045875e-05
iteration 444 res= 5.135836217469328e-05
iteration 445 res= 5.0667116817541413e-05
iteration 446 res= 4.998517529233387e-05
iteration 447 res= 4.931241236718748e-05
iteration 448 res= 4.8648704496101015e-05
iteration 449 res= 4.799392979629569e-05
iteration 450 res= 4.734796802576308e-05
iteration 451 res= 4.671070056123056e-05
iteration 452 res= 4.6082010376294676e-05
iteration 453 res= 4.5461782019967755e-05
iteration 454 res= 4.484990159541714e-05
iteration 455 res= 4.4246256739077124e-05
iteration 456 res= 4.3650736600010144e-05
iteration 457 res= 4.306323181946826e-05
iteration 458 res= 4.248363451088521e-05
iteration 459 res= 4.1911838239960475e-05
iteration 460 res= 4.134773800519988e-05
iteration 461 res= 4.079123021857772e-05
iteration 462 res= 4.024221268644769e-05
iteration 463 res= 3.970058459088125e-05
iteration 464 res= 3.916624647106197e-05
iteration 465 res= 3.863910020503077e-05
iteration 466 res= 3.8119048991660974e-05
iteration 467 res= 3.76059973328813e-05
iteration 468 res= 3.709985101613389e-05
iteration 469 res= 3.660051709702587e-05
iteration 470 res= 3.610790388229507e-05
iteration 471 res= 3.562192091298503e-05
iteration 472 res= 3.514247894774607e-05
iteration 473 res= 3.4669489946539146e-05
iteration 474 res= 3.420286705435915e-05
iteration 475 res= 3.37425245853845e-05
iteration 476 res= 3.3288378007156925e-05
iteration 477 res= 3.2840343925094645e-05
iteration 478 res= 3.239834006713884e-05
iteration 479 res= 3.1962285268688524e-05
iteration 480 res= 3.1532099457647686e-05
iteration 481 res= 3.1107703639726114e-05
iteration 482 res= 3.068901988394833e-05
iteration 483 res= 3.027597130832257e-05
iteration 484 res= 2.9868482065735287e-05
iteration 485 res= 2.946647732997104e-05
iteration 486 res= 2.9069883282018588e-05
iteration 487 res= 2.867862709650759e-05
iteration 488 res= 2.829263692830239e-05
iteration 489 res= 2.7911841899338778e-05
iteration 490 res= 2.7536172085563784e-05
iteration 491 res= 2.7165558504156563e-05
iteration 492 res= 2.6799933100765415e-05
iteration 493 res= 2.6439228737106854e-05
iteration 494 res= 2.608337917857789e-05
iteration 495 res= 2.573231908208925e-05
iteration 496 res= 2.5385983984070583e-05
iteration 497 res= 2.5044310288672817e-05
iteration 498 res= 2.470723525599373e-05
iteration 499 res= 2.4374696990668594e-05
iteration 500 res= 2.4046634430401687e-05
iteration 501 res= 2.3722987334818623e-05
iteration 502 res= 2.3403696274379752e-05
iteration 503 res= 2.3088702619435876e-05
iteration 504 res= 2.2777948529512922e-05
iteration 505 res= 2.2471376942663608e-05
iteration 506 res= 2.2168931564975176e-05
iteration 507 res= 2.1870556860259726e-05
iteration 508 res= 2.1576198039809904e-05
iteration 509 res= 2.1285801052406997e-05
iteration 510 res= 2.0999312574309247e-05
iteration 511 res= 2.071667999952068e-05
iteration 512 res= 2.043785143011736e-05
iteration 513 res= 2.0162775666714125e-05
iteration 514 res= 1.989140219902347e-05
iteration 515 res= 1.9623681196636335e-05
iteration 516 res= 1.9359563499849787e-05
iteration 517 res= 1.909900061062938e-05
iteration 518 res= 1.8841944683702867e-05
iteration 519 res= 1.85883485177851e-05
iteration 520 res= 1.8338165546922517e-05
iteration 521 res= 1.8091349831884513e-05
iteration 522 res= 1.7847856051797605e-05
iteration 523 res= 1.7607639495784343e-05
iteration 524 res= 1.7370656054736424e-05
iteration 525 res= 1.713686221327785e-05
iteration 526 res= 1.690621504169862e-05
iteration 527 res= 1.6678672188101078e-05
iteration 528 res= 1.6454191870638842e-05
iteration 529 res= 1.623273286985605e-05
iteration 530 res= 1.601425452103128e-05
iteration 531 res= 1.579871670682953e-05
iteration 532 res= 1.558607984982773e-05
iteration 533 res= 1.5376304905331567e-05
iteration 534 res= 1.516935335415719e-05
iteration 535 res= 1.4965187195581627e-05
iteration 536 res= 1.476376894031399e-05
iteration 537 res= 1.4565061603707477e-05
iteration 538 res= 1.4369028698839128e-05
iteration 539 res= 1.4175634229943817e-05
iteration 540 res= 1.3984842685692605e-05
iteration 541 res= 1.3796619032749444e-05
iteration 542 res= 1.3610928709304762e-05
iteration 543 res= 1.3427737618703556e-05
iteration 544 res= 1.3247012123266038e-05
iteration 545 res= 1.3068719038004486e-05
iteration 546 res= 1.289282562457711e-05
iteration 547 res= 1.2719299585314775e-05
iteration 548 res= 1.2548109057262132e-05
iteration 549 res= 1.237922260627345e-05
iteration 550 res= 1.2212609221338485e-05
iteration 551 res= 1.2048238308779716e-05
iteration 552 res= 1.188607968673549e-05
iteration 553 res= 1.1726103579582185e-05
iteration 554 res= 1.156828061239096e-05
iteration 555 res= 1.1412581805677036e-05
iteration 556 res= 1.1258978569940574e-05
iteration 557 res= 1.110744270051596e-05
iteration 558 res= 1.095794637235184e-05
iteration 559 res= 1.081046213486455e-05
iteration 560 res= 1.0664962906979168e-05
iteration 561 res= 1.0521421972097922e-05
iteration 562 res= 1.0379812973207776e-05
iteration 563 res= 1.02401099080379e-05
iteration 564 res= 1.010228712430714e-05
iteration 565 res= 9.966319314980428e-06
iteration 566 res= 9.832181513645008e-06
iteration 567 res= 9.69984908991285e-06
iteration 568 res= 9.569297744906288e-06
iteration 569 res= 9.440503506792493e-06
iteration 570 res= 9.313442726390805e-06
iteration 571 res= 9.188092072787502e-06
iteration 572 res= 9.06442852913864e-06
iteration 573 res= 8.942429388357293e-06
iteration 574 res= 8.82207224896801e-06
iteration 575 res= 8.703335011027128e-06
iteration 576 res= 8.586195872026307e-06
iteration 577 res= 8.470633322907103e-06
iteration 578 res= 8.356626144093586e-06
iteration 579 res= 8.244153401636597e-06
iteration 580 res= 8.133194443327082e-06
iteration 581 res= 8.023728894892497e-06
iteration 582 res= 7.915736656345503e-06
iteration 583 res= 7.80919789814618e-06
iteration 584 res= 7.704093057738765e-06
iteration 585 res= 7.600402835765889e-06
iteration 586 res= 7.4981081927095395e-06
iteration 587 res= 7.3971903452629446e-06
iteration 588 res= 7.297630762941992e-06
iteration 589 res= 7.199411164632711e-06
iteration 590 res= 7.102513515340702e-06
iteration 591 res= 7.006920022761053e-06
iteration 592 res= 6.912613134055194e-06
iteration 593 res= 6.819575532644836e-06
iteration 594 res= 6.727790135041338e-06
iteration 595 res= 6.637240087629313e-06
iteration 596 res= 6.547908763678265e-06
iteration 597 res= 6.459779760229912e-06
iteration 598 res= 6.372836895085226e-06
iteration 599 res= 6.287064203851571e-06
iteration 600 res= 6.202445936994604e-06
iteration 601 res= 6.118966556987064e-06
iteration 602 res= 6.036610735373944e-06
iteration 603 res= 5.955363350061507e-06
iteration 604 res= 5.875209482442667e-06
iteration 605 res= 5.796134414729216e-06
iteration 606 res= 5.71812362721007e-06
iteration 607 res= 5.641162795601906e-06
iteration 608 res= 5.565237788423219e-06
iteration 609 res= 5.490334664359374e-06
iteration 610 res= 5.4164396697919006e-06
iteration 611 res= 5.3435392361570486e-06
iteration 612 res= 5.2716199775160315e-06
iteration 613 res= 5.2006686881518145e-06
iteration 614 res= 5.130672340018863e-06
iteration 615 res= 5.06161808047913e-06
iteration 616 res= 4.993493229782646e-06
iteration 617 res= 4.9262852789518515e-06
iteration 618 res= 4.85998188729668e-06
iteration 619 res= 4.7945708802724135e-06
iteration 620 res= 4.730040247140621e-06
iteration 621 res= 4.66637813883937e-06
iteration 622 res= 4.603572865821133e-06
iteration 623 res= 4.5416128957983994e-06
iteration 624 res= 4.480486851750106e-06
iteration 625 res= 4.4201835097893405e-06
iteration 626 res= 4.360691797033931e-06
iteration 627 res= 4.302000789688107e-06
iteration 628 res= 4.244099710975403e-06
iteration 629 res= 4.186977929129377e-06
iteration 630 res= 4.130624955521918e-06
iteration 631 res= 4.075030442659058e-06
iteration 632 res= 4.0201841823208405e-06
iteration 633 res= 3.966076103706722e-06
iteration 634 res= 3.912696271568329e-06
iteration 635 res= 3.86003488429401e-06
iteration 636 res= 3.8080822722904142e-06
iteration 637 res= 3.7568288960497217e-06
iteration 638 res= 3.7062653445034985e-06
iteration 639 res= 3.6563823331996897e-06
iteration 640 res= 3.6071707026723356e-06
iteration 641 res= 3.5586214167356094e-06
iteration 642 res= 3.5107255608072627e-06
iteration 643 res= 3.463474340316391e-06
iteration 644 res= 3.4168590790339492e-06
iteration 645 res= 3.370871217505833e-06
iteration 646 res= 3.3255023115017745e-06
iteration 647 res= 3.280744030427176e-06
iteration 648 res= 3.236588155799916e-06
iteration 649 res= 3.1930265797655646e-06
iteration 650 res= 3.150051303608711e-06
iteration 651 res= 3.1076544362334433e-06
iteration 652 res= 3.0658281927891697e-06
iteration 653 res= 3.0245648931857067e-06
iteration 654 res= 2.983856960675397e-06
iteration 655 res= 2.9436969205427534e-06
iteration 656 res= 2.904077398621111e-06
iteration 657 res= 2.864991120019277e-06
iteration 658 res= 2.8264309077615696e-06
iteration 659 res= 2.788389681465906e-06
iteration 660 res= 2.7508604560303707e-06
iteration 661 res= 2.7138363404064147e-06
iteration 662 res= 2.6773105362294196e-06
iteration 663 res= 2.641276336678407e-06
iteration 664 res= 2.6057271252358457e-06
iteration 665 res= 2.5706563743438057e-06
iteration 666 res= 2.53605764436854e-06
iteration 667 res= 2.5019245823286456e-06
iteration 668 res= 2.46825092074931e-06
iteration 669 res= 2.4350304764982616e-06
iteration 670 res= 2.402257149701609e-06
iteration 671 res= 2.3699249225272784e-06
iteration 672 res= 2.3380278581877634e-06
iteration 673 res= 2.306560099758589e-06
iteration 674 res= 2.2755158691938053e-06
iteration 675 res= 2.2448894661681432e-06
iteration 676 res= 2.2146752670936335e-06
iteration 677 res= 2.184867724077224e-06
iteration 678 res= 2.155461363893706e-06
iteration 679 res= 2.1264507869872354e-06
iteration 680 res= 2.097830666456397e-06
iteration 681 res= 2.0695957471048042e-06
iteration 682 res= 2.0417408444815867e-06
iteration 683 res= 2.014260843891721e-06
iteration 684 res= 1.987150699483038e-06
iteration 685 res= 1.9604054333288275e-06
iteration 686 res= 1.934020134502603e-06
iteration 687 res= 1.9079899581659867e-06
iteration 688 res= 1.882310124658619e-06
iteration 689 res= 1.856975918710625e-06
iteration 690 res= 1.8319826884688917e-06
iteration 691 res= 1.8073258447014453e-06
iteration 692 res= 1.783000859970856e-06
iteration 693 res= 1.7590032677308854e-06
iteration 694 res= 1.7353286615688337e-06
iteration 695 res= 1.71197269439719e-06
iteration 696 res= 1.6889310776050814e-06
iteration 697 res= 1.666199580323052e-06
iteration 698 res= 1.6437740286169981e-06
iteration 699 res= 1.621650304734221e-06
iteration 700 res= 1.5998243463459824e-06
iteration 701 res= 1.5782921457963727e-06
iteration 702 res= 1.5570497493638638e-06
iteration 703 res= 1.5360932565399734e-06
iteration 704 res= 1.5154188193263022e-06
iteration 705 res= 1.4950226415000082e-06
iteration 706 res= 1.4749009779456512e-06
iteration 707 res= 1.455050133940327e-06
iteration 708 res= 1.435466464497653e-06
iteration 709 res= 1.4161463736951877e-06
iteration 710 res= 1.3970863139928314e-06
iteration 711 res= 1.3782827855934943e-06
iteration 712 res= 1.3597323358252036e-06
iteration 713 res= 1.3414315584948327e-06
iteration 714 res= 1.3233770932015753e-06
iteration 715 res= 1.3055656248207807e-06
iteration 716 res= 1.2879938828426462e-06
iteration 717 res= 1.270658640753805e-06
iteration 718 res= 1.253556715467175e-06
iteration 719 res= 1.2366849667609636e-06
iteration 720 res= 1.2200402966671045e-06
iteration 721 res= 1.2036196489067218e-06
iteration 722 res= 1.1874200083461574e-06
iteration 723 res= 1.1714384004149948e-06
iteration 724 res= 1.1556718905835103e-06
iteration 725 res= 1.1401175838518194e-06
iteration 726 res= 1.1247726241235269e-06
iteration 727 res= 1.1096341937759764e-06
iteration 728 res= 1.0946995131584455e-06
iteration 729 res= 1.0799658399292605e-06
iteration 730 res= 1.0654304687368892e-06
iteration 731 res= 1.0510907305852289e-06
iteration 732 res= 1.0369439924729151e-06
iteration 733 res= 1.0229876567448934e-06
iteration 734 res= 1.00921916077599e-06
iteration 735 res= 9.956359764229129e-07
iteration 736 res= 9.822356095584763e-07
iteration 737 res= 9.69015599597038e-07
iteration 738 res= 9.559735191122492e-07
iteration 739 res= 9.43106973335113e-07
iteration 740 res= 9.304135997168703e-07
iteration 741 res= 9.178910675255514e-07
iteration 742 res= 9.055370773850638e-07
iteration 743 res= 8.933493608625865e-07
iteration 744 res= 8.813256800824359e-07
iteration 745 res= 8.694638272415923e-07
iteration 746 res= 8.577616243224137e-07
iteration 747 res= 8.462169225451948e-07
iteration 748 res= 8.348276020990319e-07
iteration 749 res= 8.235915716896167e-07
iteration 750 res= 8.125067681691743e-07
iteration 751 res= 8.015711561598268e-07
iteration 752 res= 7.907827276660746e-07
iteration 753 res= 7.801395017552852e-07
iteration 754 res= 7.696395241210095e-07
iteration 755 res= 7.592808667389254e-07
iteration 756 res= 7.490616276227698e-07
iteration 757 res= 7.389799302771425e-07
iteration 758 res= 7.290339235477552e-07
iteration 759 res= 7.192217811418533e-07
iteration 760 res= 7.095417013597212e-07
iteration 761 res= 6.999919067685456e-07
iteration 762 res= 6.905706438513931e-07
iteration 763 res= 6.812761826778216e-07
iteration 764 res= 6.721068165976812e-07
iteration 765 res= 6.630608619774075e-07
iteration 766 res= 6.541366577986847e-07
iteration 767 res= 6.453325653833052e-07
iteration 768 res= 6.366469681500518e-07
iteration 769 res= 6.280782712756797e-07
iteration 770 res= 6.19624901370504e-07
iteration 771 res= 6.11285306228851e-07
iteration 772 res= 6.030579545639732e-07
iteration 773 res= 5.949413356654435e-07
iteration 774 res= 5.869339591822651e-07
iteration 775 res= 5.790343547915934e-07
iteration 776 res= 5.712410719976187e-07
iteration 777 res= 5.635526797973856e-07
iteration 778 res= 5.55967766459806e-07
iteration 779 res= 5.484849392413123e-07
iteration 780 res= 5.411028241550793e-07
iteration 781 res= 5.338200657273198e-07
iteration 782 res= 5.2663532669378e-07
iteration 783 res= 5.19547287800445e-07
iteration 784 res= 5.12554647548744e-07
iteration 785 res= 5.056561219612701e-07
iteration 786 res= 4.988504443358155e-07
iteration 787 res= 4.921363650150977e-07
iteration 788 res= 4.855126511836966e-07
iteration 789 res= 4.789780866039771e-07
iteration 790 res= 4.7253147139423184e-07
iteration 791 res= 4.6617162184140796e-07
iteration 792 res= 4.5989737016954087e-07
iteration 793 res= 4.5370756427507793e-07
iteration 794 res= 4.476010676312967e-07
iteration 795 res= 4.415767589377852e-07
iteration 796 res= 4.3563353203646407e-07
iteration 797 res= 4.297702956376726e-07
iteration 798 res= 4.239859731440079e-07
iteration 799 res= 4.1827950243848884e-07
iteration 800 res= 4.126498356969233e-07
iteration 801 res= 4.070959392285711e-07
iteration 802 res= 4.016167932302976e-07
iteration 803 res= 3.962113916139302e-07
iteration 804 res= 3.908787418387233e-07
iteration 805 res= 3.8561786476735427e-07
iteration 806 res= 3.804277943542147e-07
iteration 807 res= 3.753075776591097e-07
iteration 808 res= 3.702562744711308e-07
iteration 809 res= 3.652729572950021e-07
iteration 810 res= 3.6035671108933536e-07
iteration 811 res= 3.555066331611021e-07
iteration 812 res= 3.5072183292564256e-07
iteration 813 res= 3.4600143180107305e-07
iteration 814 res= 3.413445630311928e-07
iteration 815 res= 3.3675037155172694e-07
iteration 816 res= 3.322180137560019e-07
iteration 817 res= 3.2774665743523846e-07
iteration 818 res= 3.233354815589606e-07
iteration 819 res= 3.1898367614354896e-07
iteration 820 res= 3.146904421235045e-07
iteration 821 res= 3.1045499119566925e-07
iteration 822 res= 3.0627654561663276e-07
iteration 823 res= 3.0215433817482146e-07
iteration 824 res= 2.9808761195837475e-07
iteration 825 res= 2.9407562020472844e-07
iteration 826 res= 2.9011762627802075e-07
iteration 827 res= 2.8621290339398e-07
iteration 828 res= 2.82360734555949e-07
iteration 829 res= 2.78560412482052e-07
iteration 830 res= 2.7481123932007724e-07
iteration 831 res= 2.7111252665800463e-07
iteration 832 res= 2.674635953575218e-07
iteration 833 res= 2.638637753974243e-07
iteration 834 res= 2.6031240577817634e-07
iteration 835 res= 2.568088344177181e-07
iteration 836 res= 2.5335241798270376e-07
iteration 837 res= 2.499425218031463e-07
iteration 838 res= 2.4657851977463974e-07
iteration 839 res= 2.43259794176723e-07
iteration 840 res= 2.399857356665763e-07
iteration 841 res= 2.3675574304119238e-07
iteration 842 res= 2.3356922320598293e-07
iteration 843 res= 2.304255910769366e-07
iteration 844 res= 2.273242694127652e-07
iteration 845 res= 2.242646887645747e-07
iteration 846 res= 2.212462873154792e-07
iteration 847 res= 2.1826851084420018e-07
iteration 848 res= 2.1533081257108236e-07
iteration 849 res= 2.1243265308153308e-07
iteration 850 res= 2.0957350021544525e-07
iteration 851 res= 2.0675282898397254e-07
iteration 852 res= 2.0397012146165173e-07
iteration 853 res= 2.012248666840137e-07
iteration 854 res= 1.9851656055530183e-07
iteration 855 res= 1.9584470580981578e-07
iteration 856 res= 1.9320881183190242e-07
iteration 857 res= 1.9060839461785257e-07
iteration 858 res= 1.8804297668901136e-07
iteration 859 res= 1.8551208698005968e-07
iteration 860 res= 1.830152607709126e-07
iteration 861 res= 1.805520396145549e-07
iteration 862 res= 1.7812197119849072e-07
iteration 863 res= 1.7572460931404568e-07
iteration 864 res= 1.7335951377781793e-07
iteration 865 res= 1.710262503008099e-07
iteration 866 res= 1.6872439046938247e-07
iteration 867 res= 1.6645351159858759e-07
iteration 868 res= 1.642131967073945e-07
iteration 869 res= 1.6200303445657311e-07
iteration 870 res= 1.598226189910278e-07
iteration 871 res= 1.5767154998995106e-07
iteration 872 res= 1.5554943241920983e-07
iteration 873 res= 1.5345587666984125e-07
iteration 874 res= 1.513904982874736e-07
iteration 875 res= 1.493529180392627e-07
iteration 876 res= 1.4734276179861147e-07
iteration 877 res= 1.4535966046404892e-07
iteration 878 res= 1.4340324987916192e-07
iteration 879 res= 1.4147317084155282e-07
iteration 880 res= 1.3956906890976922e-07
iteration 881 res= 1.376905945131139e-07
iteration 882 res= 1.3583740268201137e-07
iteration 883 res= 1.340091531406271e-07
iteration 884 res= 1.3220551021289713e-07
iteration 885 res= 1.3042614268748452e-07
iteration 886 res= 1.286707238599359e-07
iteration 887 res= 1.2693893139848314e-07
iteration 888 res= 1.2523044730412125e-07
iteration 889 res= 1.2354495787876e-07
iteration 890 res= 1.2188215360600703e-07
iteration 891 res= 1.2024172920594486e-07
iteration 892 res= 1.1862338344336301e-07
iteration 893 res= 1.1702681916025933e-07
iteration 894 res= 1.1545174319605323e-07
iteration 895 res= 1.1389786635284867e-07
iteration 896 res= 1.1236490329660655e-07
iteration 897 res= 1.1085257253206048e-07
iteration 898 res= 1.0936059639531389e-07
iteration 899 res= 1.0788870090857069e-07
iteration 900 res= 1.064366158168244e-07
iteration 901 res= 1.0500407449788775e-07
iteration 902 res= 1.0359081389808867e-07
iteration 903 res= 1.0219657449514719e-07
iteration 904 res= 1.0082110031841437e-07
iteration 905 res= 9.946413880115846e-08
iteration 906 res= 9.812544075649527e-08
iteration 907 res= 9.680476038158752e-08
iteration 908 res= 9.55018551850251e-08
iteration 909 res= 9.421648592702114e-08
iteration 910 res= 9.29484165778528e-08
iteration 911 res= 9.169741430804803e-08
iteration 912 res= 9.046324940529925e-08
iteration 913 res= 8.924569525261092e-08
iteration 914 res= 8.804452829527091e-08
iteration 915 res= 8.68595279526889e-08
iteration 916 res= 8.569047665990594e-08
iteration 917 res= 8.453715975411738e-08
iteration 918 res= 8.339936544890507e-08
iteration 919 res= 8.227688484302962e-08
iteration 920 res= 8.116951180452808e-08
iteration 921 res= 8.007704302206019e-08
iteration 922 res= 7.899927788707622e-08
iteration 923 res= 7.793601851551766e-08
iteration 924 res= 7.688706965305718e-08
iteration 925 res= 7.585223869550687e-08
iteration 926 res= 7.483133563158026e-08
iteration 927 res= 7.382417301327133e-08
iteration 928 res= 7.2830565902418e-08
iteration 929 res= 7.185033185182385e-08
iteration 930 res= 7.088329086382967e-08
iteration 931 res= 6.992926537376562e-08
iteration 932 res= 6.89880802233038e-08
iteration 933 res= 6.805956257746761e-08
iteration 934 res= 6.714354194083447e-08
iteration 935 res= 6.62398501292952e-08
iteration 936 res= 6.534832118726878e-08
iteration 937 res= 6.44687914460969e-08
iteration 938 res= 6.360109936853967e-08
iteration 939 res= 6.274508564593256e-08
iteration 940 res= 6.19005931011416e-08
iteration 941 res= 6.10674666797327e-08
iteration 942 res= 6.024555337945785e-08
iteration 943 res= 5.9434702297375824e-08
iteration 944 res= 5.863476454380418e-08
iteration 945 res= 5.784559323744389e-08
iteration 946 res= 5.706704346625098e-08
iteration 947 res= 5.6298972276648284e-08
iteration 948 res= 5.554123863900513e-08
iteration 949 res= 5.47937034119908e-08
iteration 950 res= 5.405622933551291e-08
iteration 951 res= 5.3328680997499785e-08
iteration 952 res= 5.261092481322714e-08
iteration 953 res= 5.190282898413777e-08
iteration 954 res= 5.1204263492653216e-08
iteration 955 res= 5.0515100061432386e-08
iteration 956 res= 4.983521214129851e-08
iteration 957 res= 4.916447491625947e-08
iteration 958 res= 4.850276520853994e-08
iteration 959 res= 4.784996151223368e-08
iteration 960 res= 4.720594397746311e-08
iteration 961 res= 4.6570594334701625e-08
iteration 962 res= 4.5943795931809386e-08
iteration 963 res= 4.5325433664990604e-08
iteration 964 res= 4.4715394010435704e-08
iteration 965 res= 4.4113564933877674e-08
iteration 966 res= 4.351983594484714e-08
iteration 967 res= 4.2934097998508233e-08
iteration 968 res= 4.235624358136952e-08
iteration 969 res= 4.1786166555702014e-08
iteration 970 res= 4.122376225229264e-08
iteration 971 res= 4.066892741971551e-08
iteration 972 res= 4.012156015033614e-08
iteration 973 res= 3.958155996236166e-08
iteration 974 res= 3.9048827676751124e-08
iteration 975 res= 3.852326549920897e-08
iteration 976 res= 3.800477692085486e-08
iteration 977 res= 3.7493266735189495e-08
iteration 978 res= 3.6988641005454306e-08
iteration 979 res= 3.6490807098202314e-08
iteration 980 res= 3.599967359312915e-08
iteration 981 res= 3.551515029432023e-08
iteration 982 res= 3.5037148235041405e-08
iteration 983 res= 3.456557967599985e-08
iteration 984 res= 3.410035798096812e-08
iteration 985 res= 3.3641397771623444e-08
iteration 986 res= 3.318861474944605e-08
iteration 987 res= 3.27419257747687e-08
iteration 988 res= 3.230124883984027e-08
iteration 989 res= 3.186650301924314e-08
iteration 990 res= 3.143760849449175e-08
iteration 991 res= 3.101448650364991e-08
iteration 992 res= 3.059705933336045e-08
iteration 993 res= 3.018525037618878e-08
iteration 994 res= 2.9778984003512652e-08
iteration 995 res= 2.937818560555394e-08
iteration 996 res= 2.8982781590195592e-08
iteration 997 res= 2.8592699360329467e-08
iteration 998 res= 2.8207867291641614e-08
iteration 999 res= 2.782821471075797e-08
iteration 1000 res= 2.745367191832934e-08
iteration 1001 res= 2.7084170130825083e-08
iteration 1002 res= 2.6719641506027646e-08
iteration 1003 res= 2.6360019106181524e-08
iteration 1004 res= 2.6005236916249557e-08
iteration 1005 res= 2.5655229758798138e-08
iteration 1006 res= 2.5309933401439428e-08
iteration 1007 res= 2.496928440820867e-08
iteration 1008 res= 2.4633220244658277e-08
iteration 1009 res= 2.430167919494982e-08
iteration 1010 res= 2.397460041464642e-08
iteration 1011 res= 2.365192381427197e-08
iteration 1012 res= 2.3333590150686643e-08
iteration 1013 res= 2.301954096831417e-08
iteration 1014 res= 2.2709718596111936e-08
iteration 1015 res= 2.2404066160731613e-08
iteration 1016 res= 2.210252755167983e-08
iteration 1017 res= 2.1805047355670677e-08
iteration 1018 res= 2.1511570993255417e-08
iteration 1019 res= 2.1222044552023456e-08
iteration 1020 res= 2.09364148748678e-08
iteration 1021 res= 2.06546295203412e-08
iteration 1022 res= 2.0376636741481552e-08
iteration 1023 res= 2.0102385502727697e-08
iteration 1024 res= 1.9831825434654066e-08
iteration 1025 res= 1.9564906855312817e-08
iteration 1026 res= 1.9301580782869498e-08
iteration 1027 res= 1.904179881926339e-08
iteration 1028 res= 1.8785513292351325e-08
iteration 1029 res= 1.8532677152552047e-08
iteration 1030 res= 1.828324394362808e-08
iteration 1031 res= 1.8037167889275627e-08
iteration 1032 res= 1.7794403796906437e-08
iteration 1033 res= 1.7554907087980502e-08
iteration 1034 res= 1.731863380209126e-08
iteration 1035 res= 1.708554052658113e-08
iteration 1036 res= 1.6855584487074936e-08
iteration 1037 res= 1.662872344234356e-08
iteration 1038 res= 1.6404915745230843e-08
iteration 1039 res= 1.6184120306662157e-08
iteration 1040 res= 1.5966296577389088e-08
iteration 1041 res= 1.575140455148799e-08
iteration 1042 res= 1.5539404779066538e-08
iteration 1043 res= 1.5330258344526772e-08
iteration 1044 res= 1.512392681912701e-08
iteration 1045 res= 1.4920372343980318e-08
iteration 1046 res= 1.471955751391395e-08
iteration 1047 res= 1.4521445488629027e-08
iteration 1048 res= 1.4325999859465143e-08
iteration 1049 res= 1.4133184761560048e-08
iteration 1050 res= 1.3942964780826392e-08
iteration 1051 res= 1.375530497887852e-08
iteration 1052 res= 1.3570170935911059e-08
iteration 1053 res= 1.338752859436425e-08
iteration 1054 res= 1.3207344482921554e-08
iteration 1055 res= 1.302958547732663e-08
iteration 1056 res= 1.2854218954733955e-08
iteration 1057 res= 1.2681212703206011e-08
iteration 1058 res= 1.2510534953488651e-08
iteration 1059 res= 1.23421543831411e-08
iteration 1060 res= 1.2176040073365845e-08
iteration 1061 res= 1.2012161496925426e-08
iteration 1062 res= 1.185048857265106e-08
iteration 1063 res= 1.1690991639349307e-08
iteration 1064 res= 1.1533641384497688e-08
iteration 1065 res= 1.1378408915370522e-08
iteration 1066 res= 1.1225265748676194e-08
iteration 1067 res= 1.107418374149756e-08
iteration 1068 res= 1.0925135161306819e-08
iteration 1069 res= 1.0778092648538325e-08
iteration 1070 res= 1.0633029214213472e-08
iteration 1071 res= 1.0489918171960662e-08
iteration 1072 res= 1.0348733289189373e-08
iteration 1073 res= 1.020944862348161e-08
iteration 1074 res= 1.0072038612141289e-08
iteration 1075 res= 9.936478008592209e-09
iteration 1076 res= 9.802741934832806e-09
iteration 1077 res= 9.670805826797372e-09
iteration 1078 res= 9.540645454128183e-09
iteration 1079 res= 9.41223693616968e-09
iteration 1080 res= 9.285556671361011e-09
iteration 1081 res= 9.160581407871614e-09
iteration 1082 res= 9.037288199561129e-09
iteration 1083 res= 8.915654412707269e-09
iteration 1084 res= 8.795657706605298e-09
iteration 1085 res= 8.677276041063951e-09
iteration 1086 res= 8.56048770436072e-09
iteration 1087 res= 8.445271220446786e-09
iteration 1088 res= 8.331605452072502e-09
iteration 1089 res= 8.21946951843419e-09
iteration 1090 res= 8.108842826212511e-09
iteration 1091 res= 7.99970509981821e-09
iteration 1092 res= 7.892036233459359e-09
iteration 1093 res= 7.7858165069299e-09
iteration 1094 res= 7.681026401785347e-09
iteration 1095 res= 7.577646692431397e-09
iteration 1096 res= 7.47565836527734e-09
iteration 1097 res= 7.375042708263966e-09
iteration 1098 res= 7.2757812545462515e-09
iteration 1099 res= 7.177855771579152e-09
iteration 1100 res= 7.081248266708359e-09
iteration 1101 res= 6.985941026437926e-09
iteration 1102 res= 6.8919165307414326e-09
iteration 1103 res= 6.799157515882266e-09
iteration 1104 res= 6.707646957278935e-09
iteration 1105 res= 6.6173680453289e-09
iteration 1106 res= 6.528304214260109e-09
iteration 1107 res= 6.44043909576867e-09
iteration 1108 res= 6.353756560760801e-09
iteration 1109 res= 6.268240708002396e-09
iteration 1110 res= 6.183875813733907e-09
iteration 1111 res= 6.1006463918009784e-09
iteration 1112 res= 6.018537169247414e-09
iteration 1113 res= 5.937533062864534e-09
iteration 1114 res= 5.857619196447989e-09
iteration 1115 res= 5.7787808953046735e-09
iteration 1116 res= 5.701003694879439e-09
iteration 1117 res= 5.62427330100442e-09
iteration 1118 res= 5.548575621292433e-09
iteration 1119 res= 5.473896780214607e-09
iteration 1120 res= 5.400223046440084e-09
iteration 1121 res= 5.327540892355373e-09
iteration 1122 res= 5.255836961481934e-09
iteration 1123 res= 5.1850981152538785e-09
iteration 1124 res= 5.115311351106595e-09
iteration 1125 res= 5.0464638493789776e-09
iteration 1126 res= 4.978542975930983e-09
iteration 1127 res= 4.91153625988704e-09
iteration 1128 res= 4.84543138992052e-09
iteration 1129 res= 4.780216229862263e-09
iteration 1130 res= 4.715878803286345e-09
iteration 1131 res= 4.652407314088387e-09
iteration 1132 res= 4.589790087642763e-09
iteration 1133 res= 4.528015633150748e-09
iteration 1134 res= 4.467072592834716e-09
iteration 1135 res= 4.406949815414052e-09
iteration 1136 res= 4.347636221098482e-09
iteration 1137 res= 4.289120934121781e-09
iteration 1138 res= 4.231393218762223e-09
iteration 1139 res= 4.174442465497323e-09
iteration 1140 res= 4.118258217203303e-09
iteration 1141 res= 4.062830168131727e-09
iteration 1142 res= 4.008148113291236e-09
iteration 1143 res= 3.954202032032026e-09
iteration 1144 res= 3.90098202113561e-09
iteration 1145 res= 3.84847830501395e-09
iteration 1146 res= 3.7966812476117345e-09
iteration 1147 res= 3.745581320301842e-09
iteration 1148 res= 3.695169159034558e-09
iteration 1149 res= 3.6454354995319345e-09
iteration 1150 res= 3.596371209808143e-09
iteration 1151 res= 3.547967277491911e-09
iteration 1152 res= 3.50021482878355e-09
iteration 1153 res= 3.4531050680664645e-09
iteration 1154 res= 3.4066293824372943e-09
iteration 1155 res= 3.36077920571093e-09
iteration 1156 res= 3.3155461354077203e-09
iteration 1157 res= 3.2709218552726034e-09
iteration 1158 res= 3.226898177273396e-09
iteration 1159 res= 3.1834670281623035e-09
iteration 1160 res= 3.1406204175942284e-09
iteration 1161 res= 3.098350491425145e-09
iteration 1162 res= 3.0566494628772103e-09
iteration 1163 res= 3.015509716609044e-09
iteration 1164 res= 2.974923667429659e-09
iteration 1165 res= 2.9348838588637296e-09
iteration 1166 res= 2.8953829577471822e-09
iteration 1167 res= 2.856413690873222e-09
iteration 1168 res= 2.8179689395730087e-09
iteration 1169 res= 2.7800415948361533e-09
iteration 1170 res= 2.742624727375729e-09
iteration 1171 res= 2.705711465223225e-09
iteration 1172 res= 2.6692950164647728e-09
iteration 1173 res= 2.6333686949902852e-09
iteration 1174 res= 2.597925922892181e-09
iteration 1175 res= 2.5629601765799245e-09
iteration 1176 res= 2.528465022429949e-09
iteration 1177 res= 2.494434168816635e-09
iteration 1178 res= 2.4608613210024075e-09
iteration 1179 res= 2.4277403318746206e-09
iteration 1180 res= 2.3950651204516223e-09
iteration 1181 res= 2.3628296988784557e-09
iteration 1182 res= 2.3310281343777716e-09
iteration 1183 res= 2.29965458460624e-09
iteration 1184 res= 2.268703295357343e-09
iteration 1185 res= 2.238168580410086e-09
iteration 1186 res= 2.2080448405796975e-09
iteration 1187 res= 2.1783265380129035e-09
iteration 1188 res= 2.149008224093975e-09
iteration 1189 res= 2.120084505683824e-09
iteration 1190 res= 2.091550064288693e-09
iteration 1191 res= 2.0633996773649206e-09
iteration 1192 res= 2.0356281766508103e-09
iteration 1193 res= 2.008230432788692e-09
iteration 1194 res= 1.981201460265357e-09
iteration 1195 res= 1.954536273625521e-09
iteration 1196 res= 1.928229966548821e-09
iteration 1197 res= 1.902277722937253e-09
iteration 1198 res= 1.876674770477733e-09
iteration 1199 res= 1.8514164140870472e-09
iteration 1200 res= 1.8264980139159926e-09
iteration 1201 res= 1.8019149865802103e-09
iteration 1202 res= 1.7776628336842517e-09
iteration 1203 res= 1.7537370804075957e-09
iteration 1204 res= 1.7301333483844808e-09
iteration 1205 res= 1.7068473094443308e-09
iteration 1206 res= 1.683874677301291e-09
iteration 1207 res= 1.6612112315457472e-09
iteration 1208 res= 1.638852811899054e-09
iteration 1209 res= 1.6167953373237086e-09
iteration 1210 res= 1.5950347179996572e-09
iteration 1211 res= 1.5735669883179688e-09
iteration 1212 res= 1.5523881860229649e-09
iteration 1213 res= 1.53149443504141e-09
iteration 1214 res= 1.5108818906399698e-09
iteration 1215 res= 1.4905467860223901e-09
iteration 1216 res= 1.4704853549073666e-09
iteration 1217 res= 1.4506939404678133e-09
iteration 1218 res= 1.4311688962481703e-09
iteration 1219 res= 1.4119066585282868e-09
iteration 1220 res= 1.3929036574863975e-09
iteration 1221 res= 1.3741564294117918e-09
iteration 1222 res= 1.3556615105200046e-09
iteration 1223 res= 1.3374155326141478e-09
iteration 1224 res= 1.3194151182568578e-09
iteration 1225 res= 1.3016569688234359e-09
iteration 1226 res= 1.2841378343017287e-09
iteration 1227 res= 1.2668544889831696e-09
iteration 1228 res= 1.2498037703958886e-09
iteration 1229 res= 1.2329825364557167e-09
iteration 1230 res= 1.2163876908153429e-09
iteration 1231 res= 1.2000162051468249e-09
iteration 1232 res= 1.183865064113231e-09
iteration 1233 res= 1.1679313064374609e-09
iteration 1234 res= 1.1522119977150551e-09
iteration 1235 res= 1.1367042551451055e-09
iteration 1236 res= 1.1214052410867956e-09
iteration 1237 res= 1.1063121230719517e-09
iteration 1238 res= 1.0914221560055608e-09
iteration 1239 res= 1.0767326048200942e-09
iteration 1240 res= 1.0622407397478954e-09
iteration 1241 res= 1.0479439413392904e-09
iteration 1242 res= 1.0338395606736556e-09
iteration 1243 res= 1.0199249946913156e-09
iteration 1244 res= 1.0061977264807228e-09
iteration 1245 res= 9.926552109782115e-10
iteration 1246 res= 9.792949568700271e-10
iteration 1247 res= 9.66114525121961e-10
iteration 1248 res= 9.531114896673566e-10
iteration 1249 res= 9.40283473149534e-10
iteration 1250 res= 9.276280919499575e-10
iteration 1251 res= 9.151430479528823e-10
iteration 1252 res= 9.028260518263917e-10
iteration 1253 res= 8.906748212239188e-10
iteration 1254 res= 8.786871327281771e-10
iteration 1255 res= 8.668607937799353e-10
iteration 1256 res= 8.551936254077428e-10
iteration 1257 res= 8.436834826546312e-10
iteration 1258 res= 8.323282637562285e-10
iteration 1259 res= 8.211258766287312e-10
iteration 1260 res= 8.100742657213676e-10
iteration 1261 res= 7.991713773920857e-10
iteration 1262 res= 7.884152622794651e-10
iteration 1263 res= 7.778038964717138e-10
iteration 1264 res= 7.673353519703245e-10
iteration 1265 res= 7.570077019397168e-10
iteration 1266 res= 7.468190600401991e-10
iteration 1267 res= 7.367675460223665e-10
iteration 1268 res= 7.268513204738314e-10
iteration 1269 res= 7.170685575030357e-10
iteration 1270 res= 7.074174541221933e-10
iteration 1271 res= 6.978962539120801e-10
iteration 1272 res= 6.885031869113536e-10
iteration 1273 res= 6.792365573422021e-10
iteration 1274 res= 6.700946452608456e-10
iteration 1275 res= 6.610757718561776e-10
iteration 1276 res= 6.521782906597646e-10
iteration 1277 res= 6.434005537092209e-10
iteration 1278 res= 6.34740961462148e-10
iteration 1279 res= 6.26197907824502e-10
iteration 1280 res= 6.177698474703252e-10
iteration 1281 res= 6.094552210792002e-10
iteration 1282 res= 6.012525067085596e-10
iteration 1283 res= 5.931601856125372e-10
iteration 1284 res= 5.851767838617327e-10
iteration 1285 res= 5.773008278315825e-10
iteration 1286 res= 5.695308676550271e-10
iteration 1287 res= 5.618654993010797e-10
iteration 1288 res= 5.543032868744756e-10
iteration 1289 res= 5.468428671398299e-10
iteration 1290 res= 5.394828555213476e-10
iteration 1291 res= 5.322219020651683e-10
iteration 1292 res= 5.250586720464207e-10
iteration 1293 res= 5.179918568029817e-10
iteration 1294 res= 5.11020140195876e-10
iteration 1295 res= 5.041422784751226e-10
iteration 1296 res= 4.973569670454261e-10
iteration 1297 res= 4.90662988404749e-10
iteration 1298 res= 4.840591106287326e-10
iteration 1299 res= 4.775441089328586e-10
iteration 1300 res= 4.711167919691436e-10
iteration 1301 res= 4.647759834632064e-10
iteration 1302 res= 4.585205094351367e-10
iteration 1303 res= 4.523492389254035e-10
iteration 1304 res= 4.46261032925739e-10
iteration 1305 res= 4.402547543618428e-10
iteration 1306 res= 4.343293140624933e-10
iteration 1307 res= 4.2848363699424474e-10
iteration 1308 res= 4.2271662538419993e-10
iteration 1309 res= 4.17027240231775e-10
iteration 1310 res= 4.1141443150475467e-10
iteration 1311 res= 4.0587717046919267e-10
iteration 1312 res= 4.004144250372296e-10
iteration 1313 res= 3.950252088911881e-10
iteration 1314 res= 3.897085161557282e-10
iteration 1315 res= 3.8446338836486094e-10
iteration 1316 res= 3.792888658831421e-10
iteration 1317 res= 3.741839801103576e-10
iteration 1318 res= 3.691477862995619e-10
iteration 1319 res= 3.641793989184443e-10
iteration 1320 res= 3.592778675631295e-10
iteration 1321 res= 3.5444230386704856e-10
iteration 1322 res= 3.4967183220382564e-10
iteration 1323 res= 3.449655590165114e-10
iteration 1324 res= 3.4032263677646577e-10
iteration 1325 res= 3.357421885563493e-10
iteration 1326 res= 3.31223417590719e-10
iteration 1327 res= 3.2676544338166247e-10
iteration 1328 res= 3.2236747049663556e-10
iteration 1329 res= 3.1802869702986293e-10
iteration 1330 res= 3.1374831234992385e-10
iteration 1331 res= 3.0952553951341586e-10
iteration 1332 res= 3.0535961080531687e-10
iteration 1333 res= 3.012497413687285e-10
iteration 1334 res= 2.9719518930491583e-10
iteration 1335 res= 2.9319520613722225e-10
needed 1335 iterations
import matplotlib.pyplot as plt
plt.yscale('log')
plt.plot (errhist);
Experimenting with the mesh-size \(h\), we observe experimentally that the number of iterations and thus the condition number grow proportional to \(h^{-2}\). This can be easily calculated for a finite difference discretization on a uniform mesh. We will prove it for finite elements later.
from ngsolve.webgui import Draw
Draw (gfu);
Excercise:
experiment with the relaxation parameter \(\alpha\), how do the iteration numbers change ?
halve the mesh-size, how do the iteration number change ?
modify the parameter in front of the
u*vterm of the bilinear form. How does the iteration number change ?