#05 (09/06/2023)

Another example of error analysis in numerical integration

numint.jpg
The (left) rectangular rule is expressed as
Rn = h ( f0 + f1 + f2 + f3 + …+ fn−1).
It was shown that
I  ∼ Rn + A h.
(1)
By halving the step size, one gets

I  ∼ R2 n + A h

2
.
(2)
Subtracting Eq.(1) from twice Eq(2), one obtains
I  ∼ 2 R2 nRn,
(3)
which eliminates the error in the order of h. Note that if h is the step size for 2 n partitions, the step size for n partitions is 2 h.
Hence,

I
 ∼ 
2 R2 nRn
=
2 h ( f0 + f1 + f2 + f3 + f4 + …+ f2 n − 1) − (2 h) (f0 + f2 + f4 + f6 + …+ f2 n − 2)
=
2 h (f1 + f3 + f5 + f7 + …+ f2 n − 1).
(4)
This is called the mid-point rectangular rule and is just as accurate as the trapezoidal rule.

Example


f(x) = 8 x2

 

2 − x2
 
,    
1

0 
f(x) dx = π.
  1. Left rectangular rule (5 points)

    I  ∼ 0.2 ( f(0) + f(0.2) + f(0.4) +f(0.6) + f(0.8)) = 2.36867.
    Way too underestimated (see the figure).

    hw_02_sol_1.jpg
  2. Mid point rule (5 points)

    I  ∼ 0.2 ( f(0.1) + f(0.3) + f(0.5) + f(0.7)+f(0.9)) = 3.1279.
    Much improved over the left rectangular rule.

    hw_02_sol_2.jpg
  3. Trapezoidal rule

    I  ∼  0.2

    2
    ( f(0) + 2 ×(f(0.2) + f(0.4) + f(0.6) + f(0.8)) + f(1.0) ) = 3.16867.
    The accuracy is the same as the midpoint rectangular rule.

    hw_02_sol_3.jpg

Some basics on infinite series

Only in rare occasions can we sum up an infinite series in a closed form (Fourier series, for example) hence it is necessary to carry out numerical approximation for most of infinite series. Therefore, it is extremely important to be able to know in advance whether a given infinite series converges or diverges.
s=0;
for i=1:100 
 s=s+1.0/i;
end;

fprintf('sum=%f\n',s);
Online Octave (Matlab)


#include <stdio.h>
int main()
{
double s=0; int i;
for (i=1;i<100;i++) s=s + 1.0/i;
printf("sum=%f\n",s);
return 0;
}
Online C compiler


Example
100

i=1 
1

i
≈ 5.187,     1000

i=1 
1

i
≈ 7.485,     5000

i=1 
1

i
≈ 9.094     10000

i=1 
1

i
≈ 9.787,
From the above, one tends to think that ∑1/n converges to a value around 10. In fact, the series ∑1/n diverges as n → ∞ but its divergence speed is so slow that an illusion follows.

The Riemann zeta (ζ) function (p-series)

The most important infinite series that can be used as a reference series is the Riemann zeta (ζ) function defined as
ζ(p) ≡

n=1 
1

np
.
(5)

p = 1

3
ζ(1/3) = 1 + 1

3

2
+ 1

3

3
+ 1

3

4
+ …
p = 1

2
ζ(1/2) = 1 + 1

√2
+ 1

√3
+ 1

√4
+ …
p = 1
ζ(1) = 1 + 1

2
+ 1

3
+ 1

4
+ …
p = 2
ζ(2) = 1 + 1

22
+ 1

32
+ 1

42
+ …
p = 3
ζ(3) = 1 + 1

23
+ 1

33
+ 1

43
+ ……
Theorem: (Important) The p-series converges when p > 1.
(Proof) pseries1.jpg
For p < 1, it can be seen from the figure above that
1 + 1

2p
+ 1

3p
+ 1

4p
+ …+ 1

np
>

n+1

1 
1

xp
dx
=
1

1 − p
( (1 + n)1−p − 1 )
∞    as     n → ∞.
(6)
For p = 1, the above needs to be modified as
1 + 1

2
+ 1

3
+ 1

4
+ …+ 1

n
>

n+1

1 
1

x
dx
=
ln (n + 1)
∞    as     n → ∞.
(7)
For p > 1, pseries2.jpg

1

2p
+ 1

3p
+ 1

4p
+ …+ 1

np
<

n

1 
1

xp
dx
=
1

p − 1

1 − 1

np−1

1

p − 1
    as     n → ∞.
(8)
It is seen that ∑1/n10 converges faster than ∑1/n3.

Asymptotic notation and Landau-Bachmann magnitude (Big Oh)

The convergence or divergence of an infinite series can be determined by comparing the given series with another series whose convergence/divergence is already known by some other means. The following two definitions can be used to associate the given series with another series.

Definition (Asymptotic notation)

We say that f(x) is asymptotic to g(x) as xx0, i.e.
f(x)  ∼ g(x)     as     xx0
(9)
when

lim
xx0 
f(x)

g(x)
= 1.
(10)

Definition (Bachmann-Landau order of magnitude, aka Big Oh)

We say that f(x) is the Landau order of g(x), i.e.
f(x) = O(g(x)),
(11)
when |f(x)/g(x)| is bounded as xx0.
The Big Oh is less restrictive than the asymptotic notation. Note the equal sign (=) used in the Big Oh.

Examples


  1. 3 x4 + x + 8

    x2 + 2
     ∼ 3 x2     as     x → ∞,

  2. 3 x4 + x + 8

    x2 + 2
     ∼ 4     as     x → 0,

  3. 3 x4 + x + 8

    x2 + 2
    = O(x2)     as     x → ∞,

  4. 3 x4 + x + 8

    x2 + 2
    = O(x3)     as     x → ∞.

Convergence of infinite series

THEOREM (Comparison Test)

Two series, ∑an and ∑bn, of positive terms converge or diverge simultaneously if an  ∼ bn as n → ∞.

THEOREM (Comparison Test 2)

If an = O (bn) and ∑bn converges, ∑an converges. The converse is NOT true, i.e. the convergence of bn is a sufficient condition for the convergence of an but not a necessary condition.

Counterexamples


1

n3
= O(1),     1

n3
= O( 1

n
),    1

n3
= O( 1

n2
)     n → ∞.

THEOREM (Ratio Test)

Consider a series ∑an of positive terms where |an+1/an|  ∼ r as n → ∞. The series converges if r < 1, diverges if r > 1, no information is gained if r = 1.

Example

The series


n=1 
n

3n
converges as


an + 1

an

=




n + 1

3n+1

n

3n




=

n + 1

n
1

3

1

3
< 1     as    n→ ∞.

THEOREM (Alternating series) Leibniz's test (aka Dirichlet's test)

If an > 0 and an ↓ 0 (monotonically going to 0) as n → ∞,
S  = a1a2 + a3a4 + a5a6 − …,
(12)
converges.
Proof
As S2n+2 = S2n+ (a2n+1a2n+2), S2 < S4 < S6 < S8 …. On the other hand, as S2n+1S2n−1− (a2na2n+1), it follows S1 > S3 > S5 > S7 > …. Therefore the interval, [S2n−1, S2n], goes to 0 as n→ ∞.

Example

The infinite sum


n=1 
(−1)n + 1

n
= 1 − 1

2
+ 1

3
1

4
+ 1

5
− …,
converges as an = 1/n goes to 0 monotonically.
Note that


n=1 
1

n
= 1 + 1

2
+ 1

3
+ 1

4
+ 1

5
+ …
diverges as this is the p series with p = 1. The latter diverges slowly and the former converges slowly (to ln 21).

Exercise of infinite series




  1. n2 + 2 n −1

    n4 + 3

    3/2

     
    This series is convergent as an  ∼ 1/n3.


  2. 1

    (n + 3)3/2
    This series converges as an  ∼ 1/n1.5 (p > 1).


  3. n

    n2 + 3 ln n
    This series diverges as an  ∼ 1/n.



  4. 1 + 1

    n2

    This series diverges as an ≠ 0 as n → ∞ 2.



  5. cos n

    2 n −1

    2

     
    This series converges as
    an 1

    (2n − 1)2
     ∼  1

    4 n2
    .


  6. (−1)n ln 
    1 + 1

    n

    This series converges per Leibniz's test, i.e ∑(−1)n is bounded and
    ln 
    1 + 1

    n

    ↓ 0
    as n → ∞.


  7. 1

    x2 + n2
    This series converges as an = O(1/n2).


  8. (−1)n

    2n
    This series is convergent as |an+1/an| → 1/2 (ratio test).


  9. ln 
    n2 − 1

    n2 + 1

    This series converges as
    ln 
    n2 − 1

    n2 + 1

    =
    ln
    1 − 1

    n2

    − ln
    1 + 1

    n2

     ∼ 
    2

    n2
    .


Footnotes:

1
ln (1 + x) = x x2

2
+ x3

3
x4

4
+ …
Substitute x = 1 to get

ln 2 = 1 − 1

2
+ 1

3
1

4
+ …
2 Theorem: If ∑an converges, an → 0 as n → ∞.
(Proof): Assume


i=1 
ai = S.
The partial sum of an is defined as
sn n

i=1 
ai,     an = snsn−1.
As n→ ∞, both sn and sn−1 go to S. Hence, an → 0.
The equivalent statement to the above is:
If an does not go to 0 as n → ∞, ∑an diverges.


File translated from TEX by TTH, version 4.03.
On 05 Sep 2023, 22:13.