## Sunday, 30 January 2011

### Numerical Approximation

I rather not to say this is a standard / strict skill but it's just useful in MOs.

1) Why approximation?
When the answers are required to write in surd form, we can't exactly measure/calculate the answers in exact form and answer in surd (because it's irrational), therefore approximation helps us to check the answer.

2) What makes approximation accurate?
-Irrationality: The definition of irrational number is "can't be written in forms of p/q, where (p,q)=1. We often prove the irrationality of a certain number (especially in surd form) by assuming it in forms of simpliest fraction, and disprove by contradiction. Now consider a rt k lattice: Z[k^0.5].
All lattice can be written in forms of a + b k^0.5. You may notice that the lattices arranged quite far apart. These two properties are inimpotant:
i) Exist NO solution for a+b k^0.5 = c+d k^0.5 where a,c are distinct (b,d distinct)., i.e., exist unique pair for each lattice
ii) Approximately a+b k^0.5 ~ c+d k^0.5 (approximately equal, may less than 0.1), has a root that a,c has quite a large difference, so one of them is clearly be the answer.
For example, 2^0.5 - 1 = 0.41, while 11 2^0.5 - 15 = 0.55.
As a result, approximation for one and only answers seems accurate.

3) Approximation methods
- Bisection
This is one of the most famous approximation method. (as well as trisection, N-section...)
Method:
We are going to solve x from f(x) = y.
choose two integer (most proprably neighbouring integer), such that
f(N) < y, f(N+1) > y (inverted relationship if it has different behavior)
Then test f(N+0.5) > or < y, then use the next bounding to test x until a satisfied accuracy.
Of course, this is not available when the function doesn't behave monotonically.
-Numerical approximation
e.g. approximating root squares of numbers: 2011^0.5
Note that 45^2 = 2025 (this should be well known enough), while 44^2 = 45^2 - 89
2011 = 2025 - 14, so when it's rounded to nearest integer, we take 45 as the answer.
How about if we are going to estimate 1~2 d.p.?
When h is very small,
(x-h)^2 = x^2 - 2xh + h^2 ~ x^2 - 2xh.
Therefore, (x^2 - h)^0.5 ~ x - h/2x
Apply formula, (2025 - 14)^0.5  ~ 45 - 7/45 = 44.85
The error is quite small (0.06), which can be ignored for taking integer as an answer.

These are methods applied in physics quite frequently (like gravitation: g = g0(1-2h/x) ), but if it's used in mathematics properly, this is quite useful in check your answers.

This is a simple review of PC heat, HKMO heat 2011, so let's take their questions as a simple example:
1) An integer x, (x-12) and (x+19) are both perfect squares. Solve x, show that it's unique. (modified MO heat, ind. 5)
Firstly, N and N+31 are both perfect squares (x-12=N), then 2x+1 = 31, x = 15.
Check 225 = 15^2 = 237-12, 256=16^2 = 237+19.
Uniqueness: all difference of perfect square can be wrtitten in forms of 2kx+k^2. Check for 31, x is integer only when k is 1. Therefore there's only one answer.
2) given a+b = (2011^0.5 +2010 ^0.5) ^0.5, a-b = (2011^0.5 - 2010^0.5), find ab. (MO heat, ind. 3)
This is quite easy when you square both equations, and the answer is 2010^0.5 /2.
Note that identifying 2011^0.5 and 2010^0.5 by approximation is very risky, so we better write 2010^0.5 in terms of 2011^0.5.
As approximated, 2011^0.5 ~ 44.85
(2011 - 1)^0.5 ~ 44.85 - 1/2(48.5) ~ 44.84 (Exact: 44.833)
a+b = (44.85+44.83)^0.5 = (89.68) ^0.5, since this is quite far from 81 or 100, we are not going to use approximation, we use bisection to find that 89.68^0.5 ~ 9.47.
a-b = (44.85 - 44.83)^0.5 = (0.02)^0.5 = 0.141, we don't need approximation since this is quite well known that 2^0.5 = 1.41.
Solve a: a = (9.47+0.14)/2 = 4.805, b = 4.805 - 0.14 = 4.665
Multiply them, 4.805 * 4.665 = 22.42

We don't see anything special from this number, right? This question involves squares, so square this number:
22.42 ^2 = 502.6, it's quarter of 2010 (or 2011)!.

Therefore you deduce that the answer is somehow like 2011^0.5 /2, or 2010^0.5 /2, by checking you'll get the correct one.
3)Approximate [2011/5]+[2011/25]+[2011/125]+... (modified MO heat, gp. 7)
2011 is quite close to 2000 which is multiple of 125, so we expect that there won't be a big loss in [] reduction.
(*) ~ 2011 (1/5+1/25+...+1/625) -1
~ 2011 (1/4 - 1/3125) - 1
= 501.

Exercise:
1)Approximate (7-12^0.5 - (13-48^0.5)^0.5)^0.5, hence simplify the expression (MO heat, ind. 7)
2)Esimate x such that gamma(x) = 2011. (modified PC heat, E2)
3)Approximate tan 2011. (modified PC heat, E7)
4)An equilangular octagon has side length, 9,10,11,12,13,14,p,q prepectively, find pq. (modified PC heat, E14)
5)Approximate integrate (100cos5x/(1-cos10x) dx from 10/pi to 20/pi. (modified PC heat, E16)
6)ABC x BC = PQRST, where "each of its digits (except the leftmost digit), is greater than the digits on its left (like 123,24689)" is satisfied for ABC, BC and PQRST. solve PQRST.
7)i) Approximate (4956^0.5 - 3612^0.5)^2 to the nearest integer.
ii) Approximate (4959^0.5 - 3612^0.5)^2 to the nearest integer.  (modified PC09 final, D9)
8)Challanging questons
i) Compare the size of 6^0.5 and 2^0.5 +1.
ii) Compare 6^0.5 and 2^0.5 +1 by approximation.
iii) Compare the size of 303^0.5 and 16+2^0.5 by approximation.
iv) Study the relavent topics of approximation in pure maths, about approximating by differentiation, young's inequality and other skills, try (i),(ii) and (iii) again.
v) Define f: N->R, for an integer n, define S as a set that all elements are integer between [n^0.5] and [n^0.5]+1, note that [] here is the round up function.
f(n) = min{ |n^0.5 + 1 - x^0.5| } for all x in S. Describe f(n).
vi) Using the same set S. define another function g: N->N:
g(n) = x where x the x in min{ |n^0.5 + 1 - x^0.5| }.
now h: N->N is defined by h(n) = x-n. Describe h(n).
vii) Relate f(n), g(n) and h(n).
viii) Hence or otherwise, given 2^0.5 = 1.4142. Find the smallest integer, n>2 such that
I) |{n^0.5} - {2^0.5}| < 0.01
II) {{n^0.5} - {2^0.5}} < 0.01
III) |{n^0.5} - {2^0.5}| < 0.0001
IV) {{n^0.5} - {2^0.5}} < 0.0001
V) Prove that there exist no such integer n>2 that {n^0.5} = {2^0.5}.
({} is the decimal part function)

Warning: I am NOT encouring appoximating answers as a kind of answering skill in competitions or in exams. A standard calculation should ever be respected. Take this skill as fin and for checking answers only.