Prerequisites

• Single variable calculus.

• Linear algebra.

• Algorithms

Introduction

Approximation of Real number to some procession.

Pay for precision with time.

Resources

Key questions

Numerical analysis, numerical methods, or symbolic calculation

Octave, Matlab, Mathematica, Maxima, Python, or Julia

Story

William Kahan

[1] https://archive.siam.org/meetings/la09/talks/benzi.pdf

https://mathshistory.st-andrews.ac.uk/Biographies/Seidel/

Octave

Glosario

Modelo matemático. Descripción de un sistema (fenómeno, procedimiento, procedimiento …) usando la teoría (gramatica, principios, sus reglas) de alguna de las áreas de las matemáticas (análisis numérico, ecuaciones diferenciales, teoría de automatas, probabilidades, topología, …) .

Exactitud. Cualidad de conocimiento sobre la magnitud real.

Precision.  Dispersión del conjunto de valores obtenidos o medidos de un instrumento.

Sesgo o inexacitud. Diferencia entre la magnitud real y los valores obtenidos.

Incertidumbre o imprecision. Dispersión tendiendo a cero de los valores obtenidos de un instrumento.

Accuracy and precision

Bias.

ISO 5725-1 ISO/DIS 5725-1

Mathematical preliminaries and Error Analysis

1.1 Review of Calculus

Worked examples

1. Show that the following equations have at least one solution in the given intervals.
   • $xcos(x)-2x^2+3x-1=0,[0.2,0.3]\text{ and }[1.2,1.3]$

     As $f(x)=xcos(x)-2x^2+3x-1$ is continuous and

     $K=0$,

     $$f(0.2) =-0.28\le 0 \le f(0.3)=0.006009 \\$$

     The Intermediate Value Theorem implies that a number x exists, with $0.2<c_1<0.3$.

     If $f\in C[1.2,1.3]$ and 0 is a number between $f(1.2)=0.1548$ and $f(1.3)=-0.1322$, then there exists a number $c$ in $(1.2,1.3)$ for which $f(c)=0$.

1. Find intervals containing solutions to the following equations.
   • $x-3^{-x}=0$

1.2 Round-off Errors and Computer arithmetic

Def. Floor function

Def. Chopping or truncating is a function such that

Def. Suppose that $p^*$ is an approximation to $p$.

Ceil and floor

https://stackoverflow.com/questions/6208488/implementation-of-ceil-and-floor

Cast

https://stackoverflow.com/questions/22330575/how-are-typecasts-in-c-implemented

https://en.wikipedia.org/wiki/Loop_unrolling

How Many Decimals Do We Really Need?

Floating-Point Computation by Pat Sterbenz

• https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html

• https://www.jpl.nasa.gov/edu/news/2016/3/16/how-many-decimals-of-pi-do-we-really-need/

• IEEE 754

• https://www.cl.cam.ac.uk/~jrh13/slides/ogi-01mar01/slides.pdf

How calculating more precise than double or long double? How to increase precision by hundreds of decimals?

Use C++, and then use https://gmplib.org/#DOWNLOAD, other languages https://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithmetic_Library

Leijen, Daan (December 3, 2001). "Division and Modulus for Computer Scientists" (PDF). Retrieved 2014-12-25.

How can minimize the error upon arithmetic operations?

• Minimize the number of arithmetic calculations.

• Polynomials should always be expressed in the nested form before performing an evaluation.

• Use rounding over chopping.

• Prioritize the operations by error-producing sum, multiplication, and division.

Worked examples

1. Determine the six-digit a) chopping and b) rounding values of the $\phi,e$.

Chapter notes

https://nptel.ac.in/content/storage2/courses/122104019/numerical-analysis/Rathish-kumar/numerr/new4.htm

https://www.youtube.com/watch?v=JTinepDn1dI&ab_channel=OscarVeliz

Solutions of Equations in One Variable

Is there any way to find the number of real roots of a polynomial computationally?

Bisection method

Fixed-point iteration

Newton-Rapshon method

Summary

Worked examples

1. Da la definicion de numero de maquina en la forma de punto flotante decimal normalizado.

   Sea el punto flotante decimal normalizado analogo al punto flotante binario normalizado para representar las operaciones de los numeros de maquina segun el IEEE754 en base 10 y siendo inspirado en la normalizacion de la notacion cientifica (aqui tomamos $d_0=0$), a saber, el punto flotante decimal normalizado tiene la forma:

   $$\pm0.d_1d_2d_2d_3...d_i...d_k \times 10^n$$

   donde $d_1$ es distinto de 0 ($d_1\in N \text{ tal que }1\le d_1\le9$) y los siguientes terminos del significando o mantisa $d_i$ son cualquier numero menor a la base 10 ($d_i \in N \text{ tal que } 0\le d_i \le 9 \lor2\le i\le k$), 10 es nuestra base $b$, $n$ el expontente y $k$ digitos decimales del numero de maquina tal que

   $\pm(d_0+d_110^{-1}+...+d_{k-1}10^{-k+1})10^{n}=y,y\in R$

   Ejemplo:

   $y=10.15$

   $normalize(y)=0.1015\times10^2$

   porque

   $(0+1\times10^{-1}+0\times{10^0}+1\times10^{-2}+5\times10^{-3})\times10^{2}=$

   $10+0+0.1+0.5=10.15$

   2.a

   Si $lim_{x\to0}xcosx-sinx=lim_{x\to0}x-sinx=0$,

   entonces por regla de L’Hopital (*)

   $$lim_{x\to0}\dfrac{xcosx-sinx}{x-sinx}=\\ lim_{x\to0}\dfrac{\dfrac{d}{dx}(xcosx-sinx)}{\dfrac{d}{dx}(x-sinx)}=\\ lim_{x\to0}\dfrac{cosx-xsinx-cosx}{1-cosx}=\\ lim_{x\to0}\dfrac{-xsinx}{1-cosx}$$

   Si $lim_{x\to0}-xsinx=lim_{x\to0}1-cosx=0$,

   entonces por *

   $$lim_{x\to0}\dfrac{-xsinx}{1-cosx}=lim_{x\to0}\dfrac{\dfrac{d}{dx}(-xsinx)}{\dfrac{d}{dx}(1-cosx)}\\ =lim_{x\to0}\dfrac{-sinx-xcosx}{sinx}\\ =lim_{x\to0}-1-\dfrac{xcosx}{sinx}\\ =-1-lim_{x\to0}\dfrac{cosx}{\dfrac{sin}{x}}\\ =-1-\dfrac{lim_{x\to0}cosx}{lim_{x\to0}\dfrac{sin}{x}}\\= -1-\dfrac{1}{1}\\=-2$$

   2. b

Redondeo a 4 digitos.

http://www.math.usm.edu/lambers/mat460/fall09/lecture7.pdf

https://math.stackexchange.com/questions/2473794/asymptotic-order-versus-order-of-convergence

https://math.stackexchange.com/questions/976942/whats-the-formal-difference-between-analytical-and-numerical?rq=1

Interpolation

https://github.com/sanchezcarlosjr/uabc/blob/main/essays/numerical-analysis/uabc_MA_Interpolaci_n_por_el_m_todo_de_diferencias_divididas_de_Newton.pdf

https://gist.github.com/sanchezcarlosjr/6cd5f027740e964c4a45cb0880dc18ae

https://gist.github.com/sanchezcarlosjr/74ab156989087338a6d27227817a7a22

Kochanek–Bartels spline

Bezier curves

https://docs.scipy.org/doc/scipy/tutorial/interpolate.html

Numerical linear algebra

Solving Linear Systems

https://gist.github.com/sanchezcarlosjr/9edad3c66853ca24de3e97104cf68261

Gauss-Jordan

LU factorization

Approximate solutions by iterations

Exact solutions tend to be inefficiency $O(n^3)$. Our computers save us by their power processing in complex calculations. Thus the methods were born.

We say that a method approximate to the solution $x$ from an arbitrary initial vector $x^{[0]}$ where each k iteration tend to $x^{[0]},x^{[1]},x^{[2]},...,x^{[k]},...\rarr x$ such that $Ax=b$.

The method converges when $lim_{k\rarr \infty} x^{[k]}=x$, otherwise it diverges.

Jacobi method

This method was discovered by Carl Gustav Jacob Jacobi, which use triangular matrices.

https://sci-hub.do/https://doi.org/10.1080/0020739980290204

https://arxiv.org/pdf/1304.2097.pdf

https://www.coe.pku.edu.cn/attachments/dc028aad92c84efdafe6b9f65f1f0d48.pdf

https://core.ac.uk/download/pdf/82202439.pdf

Seidel method

This method was discovered by Philipp Ludwig von Seidel. We now (inappropriately) call the Gauss-Seidel method [1], which improves the Jacobi method. Honor to whom honor is due.

Methods of Conjugate Gradients

SVD

https://cims.nyu.edu/~donev/Teaching/NMI-Fall2014/Lecture5.handout.pdf

Elementary function computations

For computations with very high precision, the algorithms based on the elliptic integrals are among the fastest known today for the logarithm, the number π, and the exponential function.

Logarithms, pow, gamma,

Notes

CORDIC

https://www.jjj.de/fxt/fxtbook.pdf

Numerical differential equations

https://gist.github.com/sanchezcarlosjr/80aa8c039d71bea3decc86fb744f719f

Los métodos más comunes para resolver este tipo de problemas incluyen el método de las diferencias finitas, el método de los elementos finitos, y el método de Runge-Kutta.

Numerical analysis, numerical methods, or symbolic calculation

Random number generation

Log

1. Count the number of digits

By mod. Its time complexity is $O(n)$

def algorithmMod(n):
  count=0
  while(n>0):
    count=count+1
    n=n//10
  return count

By log. Its time complexity is $O(1)$

def algorithmLog(number):
  return math.floor(math.log10(math.abs(number)))+1

https://replit.com/join/zpwivezz-carlossanchez14

Modulo operation

Remainder after division.

Worked examples

1. Extracting individual digits.

   $$get(position,number)=trunc(\dfrac{number}{10^{position}})\text{ }mod\text{ }10$$

   • https://blog.mattclemente.com/2019/07/12/modulus-operator-modulo-operation.html
   • https://stackoverflow.com/questions/339150/extracting-individual-digits-from-a-float

Truncate

Floor and ceil

Rounding

Round half to even, a variant of the round-to-nearest method.

This method is called the round-to-even method. Other names include the round-half-to-even method, the round-ties-to-even method, and "bankers' rounding." This variant of the round-to-nearest method is also called convergent rounding, statistician's rounding, Dutch rounding, Gaussian rounding, odd–even rounding, or bankers' rounding.

Banker's rounding: the value is rounded to the nearest even number. Also known as "Gaussian rounding", and, in German, "mathematische Rundung".

Standard rounding: the value is rounded to the nearest number (be it odd or even). In German it is known as "kaufmännische Rundung".

Banker's rounding

Banker's rounding VBspeed © 2000-10, updated: 30-May-2002 Banker's rounding Banker's rounding: the value is rounded to the nearest even number. Also known as "Gaussian rounding", and, in German, "mathematische Rundung". Standard rounding: the value is rounded to the nearest number (be it odd or even). In German it is known as "kaufmnnische Rundung".

http://xbeat.net/vbspeed/i_BankersRounding.htm

754-2019 - IEEE Standard for Floating-Point Arithmetic since 1985.

https://en.wikipedia.org/wiki/Rounding

If the fractional part of x is 0.5, then y is the even integer nearest to x.

JSFiddle

Test your JavaScript, CSS, HTML or CoffeeScript online with JSFiddle code editor.

https://jsfiddle.net/2hs9nqbk/2/

function roundIt(n, d = 0) {
            var m = Math.pow(10, d); 
            var n = +(d ? n * m : n).toFixed(8);
            var i = Math.floor(n), 
                diff = n - i; // getting the difference 
            var e = 1e-8; // Rounding errors in var(diff) 
            // Checking if the difference is less than or 
            // greater than, based on that adding the 1 to it. 
            var r = (diff > 0.5 - e && diff < 0.5 + e) ? 
                ((i % 2 == 0) ? i : i + 1) : Math.round(n);
            return d ? r / m : r; // if d != 0 then returning r/m else r 
}

https://www.geeksforgeeks.org/gaussian-bankers-rounding-in-javascript/

Experimental

import time					
import numpy as np

def timer(f):
  x=np.random.rand(1,100000)[0]
  times = []
  for i in range(10):
    tic = time.perf_counter()
    f(x)
    toc = time.perf_counter()
    times.append(toc - tic)
  print(f"Build finished in {np.mean(times):0.4f} +- {np.std(times):0.4f} seconds")

Seminumerical Algorithms. Arithmetic.

Numerical analysis.

Matrix operations.

The Fast Fourier Transform

Integer and Polynomial Arithmetic

Number-Theoretic Algorithms

References

Burden, R. L. y Faires, J. D. (2015). Análisis numérico. (9a ed.).
Cengage Learning.

Chapra, S. C. (2017). Applied numerical methods with MATLAB for engineers and scientists. (4a ed.). Mcgraw-Hill Education.

Demanet, L., (2012). Introduction to numerical analysis. MIT
opencourseware.
https://ocw.mit.edu/courses/mathematics/18-330introduction-to-numerical-analysis-spring-2012/

Epperson, J. F., (2021). An introduction to numerical methods and analysis. (3a ed). Wiley.

Gezerlis, A., (2020). Numerical methods in physics with python. Cambridge University Press.

Howard II, J. P., (2020). Computational methods for numerical analysis with R. CRC Press

Fausett, L.V. (2002). Numerical methods: algorithms and applications. Pearson.

Gerald, C.F. y Wheatley, P.O. (2001). Análisis numérico con aplicaciones (6a ed.). Prentice Hall.

Stoer, J. & Bulirsch, R. (1993). Introduction to numerical analysis.Springer-Verlag.