Numerikus módszerek ZH1

ELTE IK, Programtervező informatikus BSc, C (Szoftverfejlesztő) specialization. Course owner: Krebsz Anna. ZH1 covers everything from gépi számok (machine numbers) to the Horner-algoritmus. You need at least elégséges (2) on both ZHs; either one can be retaken at the end-of-semester pót ZH.

How to use this page

Each topic has a Recipe: the exact steps you write down on the ZH.
Each recipe has a stepper. Press Next and watch the colours. Type your own numbers to check homework.
The On paper boxes show what a complete answer looks like.
Then do the Próba ZH without looking, and check with the hidden solutions.

blue: read this number orange: multiply / operate with this green: the result goes here yellow: watch this (pivot, max, rounding bit)

Sources: the official course description (inf.elte.hu dstore 227405) and the official ELTE exercise book, Bozsik & Krebsz: Numerikus módszerek példatár (dstore 224765). The notation here follows that book. No official C-group ZH1 sheet is online, so the Próba ZH is built from the same task types as the book.

ZH1 topics in syllabus order: lebegőpontos számábrázolás, hibaszámítás, Gauss-elimináció, LU-felbontás, mátrixnormák, kondíciószám, intervallumfelezés, fixponttétel [a;b]-re, Newton-módszer, Horner-algoritmus, becslés a polinom gyökeire. Jacobi, Gauss–Seidel, QR and Cholesky are not in the C syllabus.

1. Gépi számok machine numbers

A computer stores a real number as sign, mantissa and exponent. The model used at ELTE:

Definitions

A normalized machine number is a = ±m·2^k, where m = 0.m₁m₂…m_t (binary), m₁ = 1. Notation: a = ±[m₁…m_t | k].

M(t, k⁻, k⁺): t = mantissa length, k ranges over k⁻ ≤ k ≤ k⁺. Since m₁ = 1, always ½ ≤ m < 1.

ε₀ (smallest positive) = [100…0 | k⁻] = 2^k⁻−1
ε₁ (gap after 1) = [10…01 | 1] − [10…00 | 1] = 2^1−t
M_∞ (largest) = [11…1 | k⁺] = (1 − 2^−t)·2^k⁺
|M| (number of elements) = 2·2^t−1·(k⁺ − k⁻ + 1) + 1. Sign: 2 ways, m₂…m_t: 2^t−1 ways, k: (k⁺−k⁻+1) ways, +1 for zero.

Notice on the number line: inside each k the points are evenly spaced, and the spacing doubles each time k grows by one. Numbers near 0 are stored much more precisely in absolute terms.

fl(x): which machine number represents x?

Input function

fl(x) = 0 if |x| < ε₀; overflow (±∞) if |x| > M_∞; otherwise the nearest machine number (round half up). Error: |x − fl(x)| ≤ ½·ε₁·|x| = 2^−t|x|. For a concrete machine number [m|k] the book uses the bound half of the last place value: Δ = ½·2^−t·2^k.

Recipe: fl(x) in M(t,k⁻,k⁺)

Integer part to binary: divide by 2 repeatedly, read the remainders bottom to top.
Fraction part to binary: multiply by 2 repeatedly, the carries (0 or 1) are the digits, read top to bottom.
You need t+1 digits counted from the first 1 (t for the mantissa, 1 for rounding).
Normalize: move the binary point right before the first 1. Moved left by k places: exponent k. Moved right by k places: exponent −k.
Rounding digit (digit t+1) is 0: cut. It is 1: add 1 to the last mantissa digit (binary carry).
Write [m₁…m_t | k], its value, and Δ = ½·2^k−t. Check k⁻ ≤ k ≤ k⁺.

Machine addition / subtraction

Recipe: fl(a) ± fl(b)

Compute fl(a), fl(b).
Bring both to the larger exponent: shift the smaller one's mantissa right by the difference, then round it back to t digits.
Add / subtract the mantissas in binary.
Normalize again: carry out of the front means shift right and k+1; leading zeros mean shift left and k−1.
Error bound of the result: ½·2^k−t with the result's k.

M(5,−4,4):  fl(2,7) = [10110|2] = 2,75      fl(0,7) = [10110|0] = 0,6875

align 0,6875 to k=2:   0.10110·2^0 = 0.00101|10·2^2   rounding digit 1, round up
                       → [00110|2]
add:      10110
        + 00110
        = 11100      → [11100|2] = 0,875·4 = 3,5     (exact sum would be 3,4)
Δ(result) = ½·2^(2−5) = 1/16

I can do this without help

2. Hibaszámítás error bounds

Definitions

A exact value, a approximation. Δa = A − a error, |Δa| absolute error. An abszolút hibakorlát is any number ≥ |Δa| (we also write Δa for it). Relatív hibakorlát: δa = Δa / |a|.

If a is A rounded to d decimals, then Δa = ½·10^−d. Example: 1,73 is √3 to 2 decimals, so Δ = 0,005.

Propagation rules (memorize)

operation	absolute	relative
a ± b	Δa + Δb	(\|a\|δa + \|b\|δb) / \|a ± b\|
a · b	\|b\|Δa + \|a\|Δb	δa + δb
a / b	(\|b\|Δa + \|a\|Δb) / b²	δa + δb
f(a)	M₁·Δa, M₁ = max \|f′\| on [a−Δa, a+Δa]	Δf / \|f(a)\|

Rule of thumb: ± adds absolute bounds, · and / add relative bounds. Convert with Δ = δ·|value|.

Trap: subtracting close numbers

√2007 − √2006 with 44,80 − 44,79 (both 2 decimals): Δ = 0,01 and the result is 0,01, so δ = 100%. Rewrite as 1/(√2007 + √2006) ≈ 1/89,59: δ(sum) = 0,01/89,59 ≈ 0,000112 and δ(1/sum) is the same, so Δ ≈ 1,25·10⁻⁶. Same math, a million times better. This is kivonási jegyveszteség.

Task: √5·π ≈ 2,24·3,14 (both rounded to 2 decimals). Bounds?
Δ(2,24) = Δ(3,14) = 0,005
δ(2,24) = 0,005/2,24 ≈ 0,00224     δ(3,14) = 0,005/3,14 ≈ 0,00160
δ(product) = 0,00224 + 0,00160 = 0,00384
Δ(product) = 3,14·0,005 + 2,24·0,005 = 0,0269      (= δ·7,0336 check ✓)

I can do this without help

3. Gauss-elimináció solving Ax = b

Recipe

Write the augmented matrix [A | b].
Column k: the pivot is a_kk. For every row i below: l_ik = a_ik / a_kk, then S_i ← S_i − l_ik·S_k (S = sor, row). This makes a zero under the pivot.
Repeat for the next column until A is upper triangular.
Visszahelyettesítés (back substitution): last row first, x_i = (b_i − Σ_j>i a_ijx_j) / a_ii.
det A = product of the pivots, times (−1) for every row swap.

Facts they ask

Runs without row swaps ⇔ every pivot ≠ 0 ⇔ the leading principal minors (főminorok) det A₁, …, det A_n−1 ≠ 0.
Részleges főelemkiválasztás (partial pivoting): before column k, swap the row with the largest |a_ik| (i ≥ k) to the pivot place. Teljes (full): largest in the whole remaining block, rows and columns swapped (column swap renames unknowns).
Cost (műveletigény): about ⅔n³ operations.

[ 2  1 −1 | 1 ]   S2 ← S2 − 2·S1      [ 2  1 −1 | 1 ]   S3 ← S3 − (−3)·S2   [ 2  1 −1 |  1 ]
[ 4  1  0 | 6 ]   S3 ← S3 − (−1)·S1   [ 0 −1  2 | 4 ]                       [ 0 −1  2 |  4 ]
[−2  2  1 | 5 ]                       [ 0  3  0 | 6 ]                       [ 0  0  6 | 18 ]
x3 = 18/6 = 3,  x2 = (4 − 2·3)/(−1) = 2,  x1 = (1 − 1·2 + 1·3)/2 = 1
det A = 2·(−1)·6 = −12

I can do this without help

4. LU-felbontás A = L·U

LU is Gauss elimination where you keep the multipliers. L is lower triangular with 1s on the diagonal, U is upper triangular.

Recipe

Run Gauss on A alone (no b). Every multiplier l_ik goes into L at position (i,k).
U = the final upper triangular matrix. Check: L·U should give back A.
Solve Ax = b in two triangular steps: Ly = b top to bottom, then Ux = y bottom to top.
det A = u₁₁·u₂₂·…·u_nn.

Theorems (say them in Hungarian)

Létezés: Ha a Gauss-elimináció sor- és oszlopcsere nélkül végrehajtható (minden főelem ≠ 0), akkor létezik LU-felbontás. Ekvivalens: det A_k ≠ 0 (k = 1, …, n−1).
Egyértelműség: ha létezik és det A ≠ 0, akkor egyértelmű.
Direct formulas: u_ij = a_ij − Σ_k<i l_iku_kj (i ≤ j), l_ij = (a_ij − Σ_k<j l_iku_kj) / u_jj (i > j). Compute row 1 of U, column 1 of L, row 2 of U, …
Why bother: with many right-hand sides b you factor once (⅔n³) and each solve costs only about 2n².

Use the stepper above with mode = LU. Watch the green multiplier land in L each time a zero is made.

A = [1 2 1; 2 5 3; 1 0 4]
l21 = 2, l31 = 1  → [1 2 1; 0 1 1; 0 −2 3]      l32 = −2 → [1 2 1; 0 1 1; 0 0 5]
L = [1 0 0; 2 1 0; 1 −2 1]      U = [1 2 1; 0 1 1; 0 0 5]
b = (1, 1, −2):  Ly=b → y = (1, −1, −5)    Ux=y → x3 = −1, x2 = 0, x1 = 2

I can do this without help

5. Normák és kondíciószám

Vector norms

‖x‖₁ = Σ|x_i|, ‖x‖₂ = √(Σx_i²), ‖x‖_∞ = max|x_i|. Example x = (3, −4, 0): 7, 5, 4.

Norm axioms: ‖x‖ ≥ 0 and ‖x‖ = 0 ⇔ x = 0; ‖λx‖ = |λ|·‖x‖; ‖x + y‖ ≤ ‖x‖ + ‖y‖. Matrix norms also need ‖AB‖ ≤ ‖A‖·‖B‖.

Matrix norms

‖A‖₁ = oszlopnorma: largest absolute column sum. (The "1" stands upright like a column.)
‖A‖_∞ = sornorma: largest absolute row sum. (The ∞ lies flat like a row.)
‖A‖₂ = √(λ_max(AᵀA)). If A is symmetric: ‖A‖₂ = max|λ_i(A)| = ϱ(A).
‖A‖_F (Frobenius) = √(Σ a_ij²). Not induced by a vector norm.
Spectral radius: ϱ(A) ≤ ‖A‖ for every induced norm.

Kondíciószám

cond(A) = ‖A‖·‖A⁻¹‖. Properties: cond(A) ≥ 1 (induced norm); cond(cA) = cond(A); symmetric: cond₂(A) = max|λ| / min|λ|. For 2×2: cond₁ = cond_∞.

2×2 inverse: [a b; c d]⁻¹ = 1/(ad − bc) · [d −b; −c a] (swap the diagonal, negate the other two).

Perturbed right side: ‖Δx‖/‖x‖ ≤ cond(A)·‖Δb‖/‖b‖.

Perturbed matrix (if ‖A⁻¹‖·‖ΔA‖ < 1): ‖Δx‖/‖x‖ ≤ cond(A) / (1 − cond(A)·‖ΔA‖/‖A‖) · ‖ΔA‖/‖A‖. Both perturbed: same, times (‖ΔA‖/‖A‖ + ‖Δb‖/‖b‖).

Ill-conditioned example

A = [10 7; 7 5], det = 1, A⁻¹ = [5 −7; −7 10], cond_∞ = 17·17 = 289. Ax = (17, 12) gives x = (1, 1). Change b to (17,01; 11,99): x moves by (0,12; −0,17). A 0,06% change in b made a 17% change in x, which is exactly 289 times bigger.

I can do this without help

6. Intervallumfelezés bisection

Bolzano-tétel

Ha f ∈ C[a,b] és f(a)·f(b) < 0, akkor ∃x* ∈ (a,b): f(x*) = 0. If also f′ > 0 (or < 0) on (a,b), the root is unique.

Recipe

Check f(a)·f(b) < 0 (show both values). x₀ = a, y₀ = b.
Midpoint z_k = (x_k + y_k)/2, compute the sign of f(z_k).
f(z) has the same sign as f(x_k): the root is to the right, x_k+1 = z. Otherwise y_k+1 = z.
Error: |z_k − x*| ≤ (b − a)/2^k+1.
Hány lépés? Solve (b − a)/2^k+1 ≤ ε: k ≥ log₂((b − a)/ε) − 1. Example [0,1], ε = 10⁻³: 2^k+1 ≥ 1000, k ≥ 9.

I can do this without help

7. Fixpont-iteráció x = φ(x)

Rewrite f(x) = 0 as x = φ(x) and iterate x_k+1 = φ(x_k). Not every rewrite works: you have to prove it.

Banach-féle fixponttétel [a,b]-re

Ha φ: [a,b] → [a,b] kontrakció q < 1 együtthatóval (|φ(x) − φ(y)| ≤ q|x − y|), akkor (1) létezik fixpont, (2) egyértelmű, (3) ∀x₀ ∈ [a,b]-re x_k+1 = φ(x_k) konvergál hozzá, (4) |x_k − x*| ≤ q^k|x₀ − x*| és |x_k − x*| ≤ q^k/(1−q)·|x₁ − x₀|.

Practical test: φ ∈ C¹[a,b] and q = max|φ′(x)| < 1 ⇒ contraction (Lagrange mean value theorem).

Recipe: "Bizonyítsuk a konvergenciát, adjunk hibabecslést"

φ maps [a,b] into [a,b]: find φ′'s sign (monotone?), compute φ(a), φ(b); show the range is inside [a,b].
Contraction: q = max over [a,b] of |φ′(x)|, show q < 1.
Say "Banach ⇒ konvergens minden x₀ ∈ [a,b]-re".
Error: |x_k − x*| ≤ q^k(b − a) (because |x₀ − x*| ≤ b − a).
Steps for ε: q^k(b − a) ≤ ε ⇒ k ≥ ln(ε/(b−a)) / ln q (ln q < 0 flips the inequality).

x³ − 5x + 2 = 0 on [0,1],  φ(x) = (x³ + 2)/5
φ′(x) = 3x²/5 ≥ 0  → φ increasing;  φ(0) = 0,4,  φ(1) = 0,6  → φ([0,1]) = [0,4; 0,6] ⊂ [0,1] ✓
q = max |3x²/5| = 3/5 = 0,6 < 1 ✓      Banach ⇒ converges for every x0 ∈ [0,1]
|xk − x*| ≤ 0,6^k · 1.     ε = 10⁻³:  k ≥ ln(10⁻³)/ln 0,6 = 13,52  → k = 14
x0 = 0, x1 = 0,4, x2 = 0,4128, x3 = 0,41407, x4 = 0,41420  (x* = √2 − 1 = 0,41421…)

Order of convergence (konvergenciarend)

If φ′(x*) = … = φ^(p−1)(x*) = 0 but φ^(p)(x*) ≠ 0, the iteration is order p: |x_k+1 − x*| ≤ M_p/p!·|x_k − x*|^p. Plain fixed-point iteration is usually order 1, Newton is order 2.

I can do this without help

8. Newton-módszer

Formula

x_k+1 = x_k − f(x_k) / f′(x_k). Geometry: draw the tangent at x_k, x_k+1 is where it hits the x-axis.

Monoton konvergencia tétele

Ha f ∈ C²[a,b] és (1) van gyök [a,b]-ben, (2) f′ és f″ állandó előjelű [a,b]-n, (3) x₀ ∈ [a,b] és f(x₀)·f″(x₀) > 0, akkor a Newton-módszer x₀-ból monoton konvergál x*-hoz.

Lokális konvergencia: close enough to the root the convergence is másodrendű (quadratic): |x_k+1 − x*| ≤ M·|x_k − x*|², M = M₂/(2m₁), M₂ = max|f″|, m₁ = min|f′| on [a,b]. Condition: |x₀ − x*| < r = min(1/M, |x* − a|, |x* − b|).

Recipe

Check f(a)·f(b) < 0 (root exists).
Compute f′ and f″, show each keeps one sign on [a,b].
Pick x₀ = a or b where f(x₀) has the same sign as f″. Write f(x₀)·f″(x₀) > 0 ✓.
Iterate. For polynomials compute f(x_k) and f′(x_k) with Horner.

Extras, only if they show up in class

Húrmódszer (chord): x_k+1 = x_k − f(x_k)(x_k − x_s)/(f(x_k) − f(x_s)), x_s the last point where f has the opposite sign; order 1. Szelőmódszer (secant): same with x_s = x_k−1; order (1+√5)/2 ≈ 1,618.

I can do this without help

9. Becslés a polinom gyökeire where can the roots be

Tétel

P(x) = a_nxⁿ + … + a₁x + a₀, a_n ≠ 0, a₀ ≠ 0. Every (also complex) root satisfies r < |x_k| < R:

R = 1 + max(|a_n−1|, …, |a₀|) / |a_n| r = 1 / (1 + max(|a_n|, …, |a₁|) / |a₀|)

Memory aid: for R divide by the leading coefficient and take the max of all the others. For r it is the mirror image: divide by the constant term, max of all the others, then take 1 over the whole thing.

I can do this without help

10. Horner-algoritmus

Evaluate P(ξ) with only n multiplications and n additions, by bracketing: P(x) = (…((a_nx + a_n−1)x + a_n−2)x + …)x + a₀.

Recipe: the 3-row table

Row 1: all coefficients a_n … a₀. Write 0 for missing powers! (x³ − 2x − 5 is 1, 0, −2, −5.)
Bring a_n straight down to row 3.
Repeat: last result × ξ → write it in row 2 of the next column; add rows 1 and 2 → row 3.
Last number of row 3 = P(ξ). The others are the coefficients of Q(x), where P(x) = (x − ξ)·Q(x) + P(ξ).
Do Horner again on row 3 (without its last number): last number = P′(ξ).
Keep going: the j-th pass gives P^(j)(ξ)/j!, the Taylor coefficients around ξ.

P(x) = x⁵ + 6x⁴ − x³ + 3x² − 15x − 7,  ξ = 2
        1    6   −1    3   −15   −7
  2          2   16   30    66   102
        1    8   15   33    51 │ 95   ← P(2) = 95
  2          2   20   70   206
        1   10   35  103 │ 257        ← P′(2) = 257

I can do this without help

Próba ZH1 do it on paper first

Do every task on paper, then open the solution. The real ZH probably has fewer tasks; the topics are the same.

Gépi számok. M(5, −4, 4). (a) |M|, ε₀, ε₁, M_∞. (b) fl(2,7) and fl(0,7). (c) Compute fl(2,7) + fl(0,7) in machine arithmetic and give the error bound of the result.

Solution

(a) |M| = 2·2⁴·9 + 1 = 289   ε0 = 2^(−5) = 1/32   ε1 = 2^(−4) = 1/16   M∞ = (1 − 2^(−5))·16 = 15,5
(b) 2,7 = 10.1011…₂ → 0.10101|1·2²  round up → [10110|2] = 2,75    Δ = ½·2^(2−5) = 1/16
    0,7 = 0.10110|0…₂                  cut     → [10110|0] = 0,6875  Δ = ½·2^(0−5) = 1/64
(c) align to k=2: [00101|10] → round up → [00110|2];   10110 + 00110 = 11100
    result [11100|2] = 3,5,   Δ = 1/16

Hibaszámítás. (a) √5·π ≈ 2,24·3,14, both rounded to 2 decimals. Absolute and relative bound? (b) e^0,7 where 0,7 is rounded to 1 decimal. Bounds for the function value?

Solution

(a) Δ = 3,14·0,005 + 2,24·0,005 = 0,0269      δ = 0,005/2,24 + 0,005/3,14 ≈ 0,00384
(b) Δa = 0,05, f′ = eˣ, M1 = max on [0,65; 0,75] = e^0,75 ≈ 2,117
    Δf = 2,117·0,05 ≈ 0,106      δf = 0,106/e^0,7 = 0,106/2,014 ≈ 0,053

Gauss. Solve with Gauss elimination and give det A: A = [2 1 −1; 4 1 0; −2 2 1], b = (1, 6, 5).

Solution

l21 = 2, l31 = −1 → rows (0, −1, 2 | 4), (0, 3, 0 | 6);   l32 = −3 → (0, 0, 6 | 18)
x = (1, 2, 3),   det A = 2·(−1)·6 = −12

LU. LU-decompose A = [1 2 1; 2 5 3; 1 0 4] and solve Ax = (1, 1, −2).

Solution

L = [1 0 0; 2 1 0; 1 −2 1],  U = [1 2 1; 0 1 1; 0 0 5]
Ly = b: y = (1, −1, −5)     Ux = y: x = (2, 0, −1)

Normák. A = [3 1; 2 4]. ‖A‖₁, ‖A‖_∞, ‖A‖_F, cond₁, cond_∞. If b has 1% relative error (∞-norm), how big can the relative error of x be?

Solution

‖A‖1 = max(5, 5) = 5   ‖A‖∞ = max(4, 6) = 6   ‖A‖F = √(9+1+4+16) = √30 ≈ 5,477
A⁻¹ = 1/10·[4 −1; −2 3]   ‖A⁻¹‖1 = max(0,6; 0,4) = 0,6   ‖A⁻¹‖∞ = max(0,5; 0,5) = 0,5
cond1 = 5·0,6 = 3,  cond∞ = 6·0,5 = 3       δx ≤ cond·δb = 3·1% = 3%

Felezés. x³ + x − 1 = 0 on [0, 1]: 4 steps of bisection. How many steps for 10⁻³?

Solution

f(0) = −1 < 0, f(1) = 1 > 0 ✓ (and f′ = 3x² + 1 > 0 → unique)
z0 = 0,5 (f < 0) → [0,5; 1]     z1 = 0,75 (f > 0) → [0,5; 0,75]
z2 = 0,625 (f < 0) → [0,625; 0,75]   z3 = 0,6875 (f > 0) → [0,625; 0,6875]
1/2^(k+1) ≤ 10⁻³ → 2^(k+1) ≥ 1000 → k ≥ 9

Fixpont. x² − 6x + 2 = 0 on [0, 1] with x_k+1 = (x_k² + 2)/6. Prove convergence, error estimate, steps for 10⁻⁴.

Solution

φ′(x) = x/3 ≥ 0 → increasing; φ(0) = 1/3, φ(1) = 1/2 → φ([0,1]) ⊂ [0,1] ✓
q = max |x/3| = 1/3 < 1 ✓  Banach ⇒ converges ∀x0 ∈ [0,1]
|xk − x*| ≤ (1/3)^k      (1/3)^k ≤ 10⁻⁴ → k ≥ 4/lg 3 = 8,38 → k = 9
x0 = 0, x1 = 0,3333, x2 = 0,3519   (x* = 3 − √7 ≈ 0,3542)

Newton. x³ − 2x − 5 = 0 on [2, 3]. Check the monotone convergence conditions, pick x₀, do 2 steps using Horner.

Solution

f(2) = −1, f(3) = 16 ✓    f′ = 3x² − 2 > 0,  f″ = 6x > 0 on [2,3] ✓
x0 = 3: f(3)·f″(3) = 16·18 > 0 ✓
Horner at 3:  1 0 −2 −5 → 1 3 7 | 16 ;  1 3 7 → 1 6 | 25       x1 = 3 − 16/25 = 2,36
at 2,36: f = 3,4243, f′ = 14,7088                             x2 = 2,36 − 0,2328 = 2,1272
(root 2,0946)

Polinom. P(x) = 2x⁴ − 3x³ + x² − 5x + 4. (a) Bounds for |roots|. (b) P(2) and P′(2) with Horner, and Q(x) with P(x) = (x − 2)Q(x) + P(2).

Solution

(a) R = 1 + max(3,1,5,4)/2 = 3,5      r = 1/(1 + max(2,3,1,5)/4) = 1/(9/4) = 4/9
(b)      2  −3   1  −5   4
    2        4   2   6   2
         2   1   3   1 │ 6      P(2) = 6,   Q(x) = 2x³ + x² + 3x + 1
    2        4  10  26
         2   5  13 │ 27         P′(2) = 27

Puska everything on one screen

GÉPI   [m1…mt|k] = 0.m1…mt·2^k, m1=1   ε0 = 2^(k⁻−1)   ε1 = 2^(1−t)   M∞ = (1−2^−t)·2^k⁺
       |M| = 2·2^(t−1)·(k⁺−k⁻+1) + 1   fl: t+1 digits from first 1, round on digit t+1
       Δ fl(x) = ½·2^(k−t)   |x−fl(x)|/|x| ≤ ½ε1   machine op: align to larger k, round, add, normalize
HIBA   d decimals: Δ = ½·10^−d   δ = Δ/|a|   ±: Δa+Δb   ·,/: δa+δb   Δf(a) = max|f′|·Δa
GAUSS  l_ik = a_ik/a_kk,  S_i ← S_i − l_ik·S_k   det = ∏ pivots · (−1)^swaps   ⅔n³
LU     L: multipliers under 1s,  U: final matrix   Ly=b ↓ , Ux=y ↑   exists ⇔ det A_k ≠ 0
NORMA  ‖·‖1 = max column sum   ‖·‖∞ = max row sum   ‖·‖2 = √λmax(AᵀA)   ‖·‖F = √Σa²
COND   ‖A‖·‖A⁻¹‖   δx ≤ cond·δb   δx ≤ cond/(1−cond·δA)·δA   [a b;c d]⁻¹ = [d −b;−c a]/(ad−bc)
FELEZ  f(a)f(b)<0,  same sign as f(x_k) → x = z   |z_k−x*| ≤ (b−a)/2^(k+1)
FIX    φ([a,b]) ⊂ [a,b],  q = max|φ′| < 1   |x_k−x*| ≤ q^k(b−a) ≤ ε → k ≥ ln(ε/(b−a))/ln q
NEWTON x − f/f′   f′,f″ const sign, f(x0)f″(x0) > 0 → monotone   order 2, M = M2/(2m1)
GYÖK   R = 1 + max(|a_n−1|..|a_0|)/|a_n|     r = 1/(1 + max(|a_n|..|a_1|)/|a_0|)
HORNER down, ×ξ diagonal, add   last = P(ξ)   again = P′(ξ)   j-th pass = P^(j)(ξ)/j!

Szótár ZH wording → what to do

nevezetes számai	ε₀, ε₁, M_∞
elemszáma	\|M\|
a 2-nek megfeleltetett gépi szám	fl(2)
gépi kivonás / összeadás	align, operate, normalize
abszolút / relatív hibakorlát	Δ / δ
függvényérték hibája	Δf = M₁·Δa
visszahelyettesítés	back substitution
főelem, főelemkiválasztás	pivot, pivoting
főminor	upper-left k×k determinant
sornorma / oszlopnorma	‖·‖_∞ / ‖·‖₁
jól / rosszul kondicionált	small / large cond(A)
… pontossággal	error ≤ ε
Hány lépés szükséges?	solve the error bound ≤ ε for k
Bizonyítsuk a konvergenciát	Banach (fixpont) or monotone conv. tétel (Newton)
konvergenciarend	order p
helyettesítési érték	P(ξ), use Horner
Taylor-polinom ξ körül	repeated Horner

Numerikus módszerek ZH1

How to use this page

1. Gépi számok machine numbers

Definitions

fl(x): which machine number represents x?

Input function

Recipe: fl(x) in M(t,k−,k+)

Machine addition / subtraction

Recipe: fl(a) ± fl(b)

2. Hibaszámítás error bounds

Definitions

Propagation rules (memorize)

Trap: subtracting close numbers

3. Gauss-elimináció solving Ax = b

Recipe

Facts they ask

4. LU-felbontás A = L·U

Recipe

Theorems (say them in Hungarian)

5. Normák és kondíciószám

Vector norms

Matrix norms

Kondíciószám

Ill-conditioned example

6. Intervallumfelezés bisection

Bolzano-tétel

Recipe

7. Fixpont-iteráció x = φ(x)

Banach-féle fixponttétel [a,b]-re

Recipe: "Bizonyítsuk a konvergenciát, adjunk hibabecslést"

Order of convergence (konvergenciarend)

8. Newton-módszer

Formula

Monoton konvergencia tétele

Recipe

Extras, only if they show up in class

9. Becslés a polinom gyökeire where can the roots be

Tétel

10. Horner-algoritmus

Recipe: the 3-row table

Próba ZH1 do it on paper first

Puska everything on one screen

Szótár ZH wording → what to do

Recipe: fl(x) in M(t,k⁻,k⁺)