Scientific Computation WS 2001/2002
Gaston Gonnet
Date:
February 24, 2002
Contents
0
.
1
Introduction
0
.
1
.
1
Overview
0
.
1
.
2
List of used abbreviations
0
.
1
.
3
General Online Material
1
. The accurate location of an aircraft
1
.
1
Introduction
1
.
2
How to Pose the Problem as a Least Squares Problem
1
.
2
.
1
How to solve a mixed problem: equation system and minimization
1
.
3
Solving the Nonlinear Least Squares Problem
1
.
3
.
1
More Theory - The analytical method of function minimization
1
.
3
.
1
.
1
Eigenvalue / Eigenvector Decomposition
1
.
4
Error Analysis / Confidence Analysis
1
.
4
.
1
An approximation for a complicated
1
.
4
.
2
Interactive Exercises
1
.
5
Methods of function minimization
1
.
5
.
1
Analytical method (in one dimension)
1
.
5
.
2
Brent's Method (Golden Section Search in one dimension)
1
.
5
.
2
.
1
Brent's exponential search
1
.
5
.
2
.
2
Parabolic Interpolation
1
.
5
.
2
.
3
A further improvement
1
.
5
.
3
Multidimensional Methods
1
.
5
.
3
.
1
Steepest Descent
1
.
5
.
3
.
2
Brent used in a given direction
1
.
5
.
3
.
3
Random Directions
1
.
6
References and Further Reading
1
.
6
.
1
Online Material for Minimization Methods
1
.
6
.
2
Online Material for Linear Least Squares
1
.
6
.
3
Online Material for Nonlinear Least Squares
2
. Secondary Structure Prediction in Proteins
2
.
1
Introduction to Protein Biochemistry
2
.
1
.
1
The mathematical formulation of the problem
2
.
2
Least Squares - SVD
2
.
2
.
0
.
1
The need of weighting:
2
.
2
.
1
Singular Value Decomposition and Eigenvalue Decomposition
2
.
2
.
1
.
1
The Singular Value Decomposition (SVD)
2
.
2
.
1
.
2
The actual calculation of the SVD
2
.
2
.
1
.
3
Least squares using Eigenvalues
2
.
2
.
1
.
4
The relation between the SVD of
and the eigenvalue-decomposition of
2
.
2
.
2
Criteria for discarding singular values
2
.
2
.
3
A concrete example
2
.
3
Least squares - Best Basis
2
.
3
.
1
Definition of ``Best Basis''
2
.
3
.
1
.
1
Stepwise Regression
2
.
3
.
1
.
2
Difficulty of the problem
2
.
3
.
2
Formulation of the minimization-problem using ``Best Basis''
2
.
3
.
3
Algorithms for finding local minima
2
.
3
.
4
The Confidence Interval
2
.
4
Final Observations for the Least Squares Methods
2
.
4
.
1
Refining the predictor function
2
.
4
.
1
.
1
Validation
2
.
5
Linear Classification/Discrimination
2
.
6
Learning Methods - Nearest Neighbours (NN)
2
.
6
.
1
Mathematical formulation of the problem
2
.
6
.
1
.
1
The general idea
2
.
6
.
1
.
2
Application to
Helix Prediction
2
.
6
.
2
Searching and Data structures for NN problems
2
.
6
.
2
.
1
Sequential Search
2
.
6
.
2
.
2
Range Searching
2
.
6
.
2
.
3
Quad Trees
2
.
6
.
2
.
4
-d Trees (
-dimensional trees)
2
.
6
.
2
.
5
Building NN trees
2
.
6
.
2
.
6
The Cost of Building an NN tree
2
.
6
.
3
Searching the NN-tree
2
.
6
.
3
.
1
Searching the
nearest neighbours
2
.
6
.
3
.
2
Concluding a value from its neighbours
2
.
6
.
4
Practial considerations
2
.
6
.
4
.
1
Bucketing
2
.
6
.
4
.
2
Normalizing dimensions
2
.
6
.
4
.
3
Using random directions
2
.
6
.
5
NN trees used for clustering
2
.
7
Linear Programming (LP)
2
.
7
.
1
Notation/Terminology
2
.
7
.
1
.
1
Example
2
.
7
.
2
Fundamental Theorem of Linear Optimization
2
.
7
.
3
The Simplex Method
2
.
7
.
4
Solving the 'helix problem' with the simplex algorithm
2
.
7
.
5
Inconsistent data
2
.
7
.
5
.
1
Using slack variables
2
.
7
.
5
.
2
Alternative method
2
.
7
.
6
Prediction
2
.
7
.
7
Comparison of Linear Programming with Least Squares
2
.
8
Neural Networks (NNet)
2
.
8
.
1
Building a starting Random Net
2
.
8
.
2
Training the Network
2
.
8
.
3
Post Processing
2
.
9
References and Further Reading
2
.
9
.
1
Online Material
3
. Molecular Dynamics
3
.
1
Introduction
3
.
2
Simulation
3
.
3
Two Approaches to Molecular Dynamics
3
.
3
.
1
Decisions in the construction of the model
3
.
3
.
2
Challenges of molecular dynamics
3
.
3
.
3
Simulation Packages
3
.
4
Energy minimization for a protein structure
3
.
5
Automatic program generation
3
.
5
.
1
A toy problem
3
.
5
.
2
Optimization
3
.
5
.
3
Conclusions
3
.
6
Minimization Strategies for Molecular Dynamics
3
.
7
The Spectral Method for Function Minimization
3
.
7
.
1
Comparision of minimization methods
3
.
7
.
1
.
1
Final comments
3
.
8
References and further reading
3
.
8
.
1
Online material
3
.
9
The program code
4
. Stock Market Prediction
4
.
1
Introduction
4
.
1
.
1
Definitions
4
.
1
.
2
Examples of information available online
4
.
1
.
3
Rationale for Stock Market Prediction
4
.
1
.
4
Organization of the modelling
4
.
2
Optimal Transaction Sequence
4
.
2
.
1
Defining the Problem
4
.
2
.
2
The calculation of the optimal transaction sequence
4
.
2
.
3
Interactive exercise ``Optimal Transaction Sequence''
4
.
3
Approximating the Optimal Transaction Sequence
4
.
3
.
1
Decision versus Numerical approach
4
.
3
.
1
.
1
The decision problem
4
.
3
.
1
.
2
Fractal nature
4
.
3
.
1
.
3
Period data
4
.
3
.
1
.
4
The numerical problem
4
.
3
.
1
.
5
4
.
3
.
1
.
6
Constructing mathematical functions
4
.
3
.
1
.
7
Dimensionality
4
.
3
.
2
Computing good (optimal) parameters
4
.
3
.
3
Functionals to optimize
4
.
4
Simulation
4
.
4
.
1
Two simple policies
4
.
4
.
2
Optimization of simulation parameters
4
.
4
.
2
.
1
The one dimensional maximization algorithm
PiecewiseConstMax
4
.
4
.
2
.
2
Multidimensional methods
4
.
4
.
2
.
3
Note on Spiral Search and Shrinking Hypercube
4
.
4
.
2
.
4
Brute force search / Grid search
4
.
5
Confidence analysis
4
.
5
.
1
The notion of ``Transfer of error''
4
.
5
.
2
Monte Carlo estimation
4
.
6
Dynamic Programming
4
.
6
.
1
The idea of dynamic programming in more detail
4
.
7
Examples of Dynamic Programming
4
.
7
.
1
Optimal Binary Search Trees
4
.
7
.
2
Interactive Exercise ``Optimal Binary Search Tree''
4
.
7
.
3
Optimal Order of Matrix Multiplications
4
.
7
.
4
String Matching
4
.
7
.
4
.
1
Recovering the optimal alignment using only
O
(min(
m,n
)) memory
4
.
8
References and Further Reading
5
. Phylogenetic Tree Construction
5
.
1
Introduction
5
.
1
.
1
Classification types
5
.
1
.
2
Applications
5
.
2
Phylogenies with Protein Sequences
5
.
3
Distance Based Methods
5
.
4
A Model of Evolution
5
.
4
.
1
Dayhoff Matrices
5
.
4
.
2
Estimating Distances between Sequences by Maximum Likelihood
5
.
4
.
3
Distance and Variance matrices
5
.
4
.
3
.
1
How to score deletions
5
.
4
.
4
Using Dynamic Programming for Sequence Alignment (Global Alignment)
5
.
4
.
5
Interactive exercise
5
.
4
.
6
Sequence alignment using Dayhoff matrices and maximum likelihood
5
.
4
.
7
Local alignment
5
.
4
.
8
Cost free end alignment
5
.
4
.
9
Creating an Initial Topology through Neighbour Joining
5
.
4
.
10
Least Squares Fit
5
.
4
.
11
Swapping Heuristics
5
.
5
Character Based Methods
5
.
5
.
1
Parsimony
5
.
5
.
2
Strict character compatibility
5
.
5
.
2
.
1
Perfect Phylogeny (Strict Character Compatibility) Exercises
5
.
6
Genetic Algorithms
5
.
7
References and Further Reading
Bibliography
About this document ...
Gaston Gonnet, Institute for Scientific Computing, ETH Zürich, Switzerland
2002-02-24
With assistance from
SkillsOnline
and
Web Pearls
