ES1101-Computational Engineering

# ES1101

### Computational Engineering

Created by Panchatcharam Mariappan

## Disclaimer

This Presentation has been prepared based on the C: How to Program book. However, it may contain some typo and mistakes. Contact the author for any mistakes

## Marks

Components Marks
Quiz 1 10
Quiz 2 10
Assignments+Coding Marathon 10+15
Lab Exams 15
End Sem 40
Total 100

## References

• H. M. Deitel and P. J. Deitel, C: How to program, Prentice Hall India, (2014).
• S. C. Chapra and R. P. Canale, Numerical Methods for Engineers, Mc-Graw Hill, (2010).

## Moodle

Join IIT Tirupati Moodle

## Moodle

Send Assignments and Queries related to this course to

panch.m@iittp.ac.in

Onling GDB

repl.it

Jdoodle

RexTester

## Tips

• Program like a child
• Learn by doing
• Remember the syntax
• Do hand calculations or Code by hand
• Generate Unit Test
• Debug code
• Don't memorize a code, try to understand the logic
• Do little by little
• Practice! More Practice! More and More Practice!
• Don't panic while making mistakes, learn from it

## Computer Systems

Daily usage: General Purpose Machines

Specific applications: Special Purpose Machines

Defined through their interfaces at a number of layered abstraction levels

## Computer Systems

Application Programs

High-Level Languages: Set of Machine Instructions

Language Architecture: Interface between Application Program and High-Level Language

Instruction set Architecture: Interface between machine instructions set and runtime, I/O Control

## Four Basic View Points

Structure: Interconnection of various hardware components

Organization Dynamic Interplay and Management of various components

Implementation: Design of hardware components

Performance: Behaviour of the computer system

## History

Z1 (1938): First Program controlled (Mechanical Computer)

Z2 (1939): First Operational Program controlled computer with fixed point arithmetic

1940: Iowa State University, small-scale, special-purpose electronic computer, not operational

Z3 (1941): Fully functional programmable special-purpose machine (Germany)

## History

### ENIAC(1944)

Electronic Numerical Integration And Calculator

First operational general-purpose machine, 18000 vaccum tubes

For World War II, Weight: 30 tons, 1500 Sq.ft, 140kW power

Programmable through manaul switching, Very slow by today's standard, very less storage

## Von-Neumann

### EDVAC

Successor of ENIAC, 1946-1952, Electronic Discrete Variable Automatic Computer

Executes stored program

Memory buffer register, Memory address register, instruction register, instruction buffer register, program counter, accumulator, multiplier quotient.

## Von-Neumann

• EDSAC(1949): Electronic Delay Storage Automatic Calculator
• MARK I, II, III, IV
• BINAC(1949): Binary Automatic Computer
• UNIVAC(1951): Universal Automatic Computer

## Von-Neumann

• Second Generations: Transistor
• Third Generations: Integrated Circuits
• Microelectronics
• Semiconductor
• Microprocessors: 4004, 8080, 8086, ...
• Pentium I, II, III, IV, Core, Core 2

### Personal Computer

• 1977: Apple
• Atlair, Processor Techonolgy
• North Star
• Tandy
• Commodore
• ...

• Compaq
• IBM
• Dell
• HP
• Lenovo
• ...

## Hardware and Software

### Hardware and Software

Hardware: Any Physical device used in or with machines

Software: Collection of Code Installed on computers' hard drive

### Hardware and Software

• Billions of Calculations in one second
• SuperComputers: Quadrillions of instructions per second
• Computer Programs: Computer processes data under the control of sequences of instructions
• Guides the computers through ordered actions
• Guided by people: Programmers

## Moore's Law

• Hardware cost decreases rapidly
• Capacities of computers doubles every year
• Number of transistors in dense integrated circuit doubles every year

SSI,LSI,VLSI,VVLSI,UVLSI,WSI,SOC,3D-IC

## Performance

• Short Response Time
• High Throughput
• Availability
• Processing Speed
• Latency
• Bandwidth
• Power consumption
• Scalability

## Computer Organization

### Input Unit

• Keyboard
• Touch screens
• Mouse
• Voice Commands
• Scanning Images
• Barcode...

### Output Unit

• Screens
• Printed On Paper
• Audio
• Video
• ...

### Memory Unit

• CPU Registers
• Main Memory or RAM
• Secondary Storage
• HDD,SSD,USB,DVD
• ...

### ALU

• Calculations: Add, Subtract, Divide, Multiply
• Decision Making

### CPU

• Tells the ALU when information should be read from MU
• Tells the ALU when information should be used from MU
• Tells the ALU when information should be send from MU to Output
• Multi-Core Processors

## Data Hierarchy

• Bits: Smallest Data item, 0 or 1, binary digit
• Characters: Decimal digits, letters, symbols, Unicode, ASCII
• Fields: Composed of Bits, Bytes or Characters
• Records: Composed of field
• Files: Group of records
• Database: A collection of data
• Big Data

### Byte Measurements

Unit Bytes Bytes(10x)
1 KB 1024 Bytes 103
1 MB 1024 KB 106
1 GB 1024 MB 109
1 TB 1024 GB 1012
1 PB (Peta) 1024 TB 1015
1 EB (exa) 1024 PB 1018
1 ZB (Zetta) 1024 EB 1021

## Machine/Assembly/High-Level Languages

### Machine Language

It is the lowest-level programming language which only the specific computer can understand, consists of strings of numbers and almost impossible for humans to understand.

### Machine Language

• Computer can directly understand only its own ML
• Defined by its hardware design
• Strings of Numbers (0s and 1s)
• Machine Dependent
• Difficult for human to understand
• Slow and tedious for a programmer

### Assembly Language

It is a low level programming language that allows a user to write a program using alphanumeric mnemonic codes instead of numeric codes for a set of instructions. It can be translated using an assembler into machine language.

### Assembly Language

• Strings of numbers computer can understand
• English-like abbreviations
• Abbreviations are basis of AL
• Assembler: Translator programs, AL to ML
• Code is quite easier than ML to understand by human
• Need more instructions for simplest task

### High-Level Language

It is a programming language that is understood by humans/programmers. It can be translated using a translator, for example, compiler or interpreters, into a simple machine language that computer can understand and execute. It does not depend on specific computer.

### High-Level Language

• Single Statment to accomplish substantial tasks
• Compilers: Translator program HLL to ML
• Easy to understand
• Variables, Arrays,Objects,Loop
﻿

## Compiler Vs Interpreter

### What is a compiler?

A compiler is a program that reads a program written in the high-level language and converts it into the machine or low-level language and reports the errors present in the program.

It converts the entire source code in one go or could take multiple passes to do so, but at last, the user gets the compiled code which is ready to execute.

Examples: C, C++, C#, Scala

### 6 Phases of Compiler

• Lexical Analyzer: Scans the code as a stream of characters into lexemes. Output: Sequence of tokens with refernce to the programming language
• Syntax Analyzer: Tokens generated in Lexical analyzer phase are against grammar of programming language. Checks whether the expressions are syntactically correct or not. It makes parse trees

### 6 Phases of Compiler

• Semantic Analyzer: Checks whether the expressions and statements generated by previous phase follow the rule of programming language or not. Creates annotated parse trees
• Intermediate Code:Equivalent intermediate code of the source code.
• Code Optimizer:Improves space and time requirement of the program. Eliminates the redundant code

### 6 Phases of Compiler

• Code Generator:Final phase. Target code for a particular machine is generated. Performs memory, register managments and machine specific optimization

### What is an Interpreter?

An altnerative for implementing a programming language and does the same work as compiler

• It Performs lexing, parsing and type checking similar to compiler.
• Processes syntax tree directly to access expressions and executes statements rather than generating code from the syntax tree
• Require processing same syntax tree more than once. Slower than compiler
• Examples: JAVA, Python, Ruby, PHP

### Interpreters

• Large HLL to ML takes more time to compile
• Interpreters: Developed to execute HLL directly
• No compilation delay
• Slower than compiled programs
• JIT in Java, Python,Matab

### Compiler Vs Interpreter

Process Compiler Interpreter
Input Takes an entire program at a time Takes a single line of code at a time
Output Generates intermediate object code Won't produce any intermediate object code
When? Before execution Simultaneous Compilation and execution

### Compiler Vs Interpreter

Process Compiler Interpreter
Speed Faster Slower
Memory Requirment More for object code Less, no object code
Errors All errors at a time after compilation, difficult Error, line by line, easier
﻿

## History

• BCPL (1967): Basic Combined Programming Language
• B (1969): Bell Labs - Ken Thompson and Dennis Ritchie
• C (1972): Bell Labs - Dennis Ritchie
• To Develop the UNIX operating System

## Usage

• Operating System: C or C++
• Mostly Hardware independent
• Portable to Many Computers
• Embedded systems
• Real-time systems
• Communications systems

## Operating System

• A System software to manage hardware and software
• Provides common services for computer programs
• Linux,MS Windows,Google Andriod, Apple OS and so on
• Objective-C: Derived from C

## Embedded System

• Programmed, Controlled OS
• Embedded as part of a complete device
• Majority of microprocessors manufactured to target embedded navigation system, smart home appliances, smart phone, tablets, robots and so on
• C is the most popular programming for embedded

## Real-time System

• Real time-OS (RTOS): To serve real-time applications
• Processes data as it comes in, no buffer delay
• Misson critical applications, requires instantaneous response time
• Air-traffic control system, networked multimedia system

## Communication System

• System needs to route massive amounts of data to their destinations
• To deliver audio and video smoothly without delay
• Telephone,Mobile
﻿

## Book

• 1978: First Book on C
• The C Programming Language: Kernighan and Dennis Ritchie

## Variations

• Rapid Growth
• Different Variations for various type of hardware platforms
• Incompatible
• Requirement of Standard C: 1983
• American National Standards Committee on Computers and Information Processing

## ANSI

• American National Standards Institute
• 1989: ANSI X3.159-1989
• or ANSI C or Standard C
• Approved by ISO 1999: ISO C
• 1999: C99

## C11 and C18

• C11: 2011
• Expands C's capabilities: Atomic operations, multi-thread
• C18: 2017/2018
• Clarifications of defects of C11
• Technical Corrections
• No new language features
﻿

## Functions

• C Program: Pieces of blocks, functions
• Rich collection of existing functions
• C Standard Library

## How to Program

• Learning the C language itself
• Learning how to use the functions in the C Standard Library

## When Programming in C

• C Standard Library Functions
• Functions you create yourself
• Advantage: You know exactly what it does
• Disadvantage: Time consuming to design, develop, debug, tuning to perform
• Functions created by other people (open source, closed source)
﻿

## C++

• Bjarne Stroustrup: Bell Labs
• Imperative
• Object Oriented: Reusable software components
• ISO/IEC14882-1998,2003,2011,2014,2017
• C++98,C++03,C++11,C++0X,C++14,C++1y,C++17,C++1z,C++20

## Objective C

• Object Oriented C
• Developed: 1980. Acquired NeXT and then Apple
• Key programming language for OS X and iOS devices

## Java

• Sun Microsystems, 1991
• Runs on a broad variety of
• Computer systems
• Computer-controlled devices
• Write once, run anywhere
• Smart phone, Android App Development

## C#

• Microsoft's Prorgramming language
• VB,VC++,VC#
• VC#-C++ and Java
• integrating internet and web

## PHP

• Scripting language
• Millions of websites
• Platform independent
• Supports database

## Python

• 1991: National Research Institute for Mathematics and Computer Science
• Extended through classes
• Programming interfaces

## Javascript

• Scripting language
• Used to add dynamic behaviour of web pages
• Animations, interaction with user
• Major Web browsers

## Swift

• Apple's programming language for iOS: 2014
• Modern language for app-development
• Easy for beginners
• Performance and security
﻿

• Editor
• Preprocessor
• Compiler
• Execution
• Debugging

## Phase 1: Editor

• Editing or creating a C file
• gedit, vim, emacs
• Eclipse, MSVC, geany, DevC
• Store the program on secondary hard disk
• Save the file name with an extension .c

### Phase 2: Preprocessing

• While the compiler translates the C program to ML or object code
• Including other files for compilation
• Preprocessor program obeys preprocessor directives

### Phase 3: Compilation

• Compiler translates the C program to ML or object code
• Compile error due to syntax error, violating the rules of the language
• Issues an error message to fix the error
• Error message may differ from system to system

• References of functions defined elsewhere
• Object code provided by many programmers are linked
• Object code produced by the compiler has holes due to missing parts
• Links the object code for the missing functions
• Produces an executable image

### Phas 2,3 and 4

• Usually, Phase 2,3 and 4 can be done by a single command for smaller program
• gcc FileName.C
• It compiles, links and creates an executable a.out

• Before Execution
• Must be placed in memory first
• Additional components from shared libraries required for the program

## Phase 6: Execution

• Under the control of CPU
• Executes one instruction at a time
• To load and execute, ./a.out
• Provides necessary input from stdin(a keyboard)
• Produces output to stdout(a computer screen)
• stderr: to display the error to the screen

### Debugging

• Not necessary to produce error free code in first attempt
• Syntax error, runtime error, segmentation fault
• Make necessary corrections depending on the code and repeat all steps

## FirstProgram.C


#include<stdio.h> //header file
//Function main begins program execution
int main(void)




{//Body of the main begins here
printf("Hello World\n");
return 0;
}//end of function main


• The two slashes
• Insert comments to document programs
• Compiler wont perform any action (ignoers)

### Preprocessor Directive

#include<stdio.h> //header file
• stdio.h is a directive preprocessor
• Processed before compilation
• Includes the contents of the standard input output header in the program
• For printf function

### Alignments

• Give spaces and alignments
• White or blank spaces or tab

main

int main(void) //header file
• Part of every C program
• main is a building block, function
• C program contains one or more functions, one must be main
• Function can return information
• The keyword int returns an integer value
• Function can receive an information, here void, means no information received
• The body of every function starts at the left brace { and ends before the right brace }

printf

int printf(const char *format, ...);
printf("Hello World\n");
• Instructs the computer to perform an action
• Print on the screen the string characters marked by quotation marks
• f stands for formated
• Every statement must end with a semicolon, ; statment terminator
• Exact characters as they appear between quotes

### Escape Sequence

• The backslash (\) is an escape character
• The escape sequence (\n) means newline
• The escape sequence (\t) means horizontal tab
• The escape sequence (\\) means insert a backslash in string
• The escape sequence (\") means insert a double-quoter character in string
﻿

## Phase 1: Editor

• Editor: gedit
• Type the following in the editor
#include<stdio.h> //header file
//Function main begins program execution
int main(void)
{//Body of the main begins here
printf("Hello World\n");
return 0;
}//end of function main

• Save the file as FirstProgram.C in Documents directory

### Open the Terminal

• Open the terminal in Ubuntu
• Navigate to the directory where you have saved the FirstProgram.C file

### Phase 2-5:Simplest

• gcc FirstProgram.C
• It compiles, links and creates an executable a.out
• Type ./a.out

## Output

Hello World

### Phase 2-5:Recommended

• gcc FirstProgram.C -o FirstProgram
• It compiles, links and creates an executable FirstProgram
• Type ./FirstProgram
﻿

## SecondProgram.C


//Function main begins program execution
int main(void)
{//Body of the main begins here
printf("This is my First ES1101 Exercise\n");
printf("My Name is Panchatcharam\n");
printf("My Roll Number is AA8245\n");
return 0;
}//end of function main


## Output


This is my First ES1101 Exercise
My Name is Panchatcharam
My Roll Number is AA8245

﻿

## Basic Variable Data Type

• char
• int
• float
• double
• void

### Basic Variable Data Type

Variable Type Description Min Max
signed char 7 bit ASCII -127 127
unsigned char 8 bit ASCII 0 255
The minimum range is guaranteed in all compilers. See ISO C. However, it varies. See gcc range.

### Basic Variable Data Type

Variable Type Description Min Max
signed int or int signed integer 16 bit -(215)-1 215-1
unsigned short int or unsigned int unsigned integer 16 bit 0 216-1
The minimum range is guaranteed in all compilers. See ISO C. However, it varies. See gcc range.

### Basic Variable Data Type

Variable Type Description Min Max
long int signed integer 32 bit -(231)-1 231-1
unsigned long int unsigned integer 32 bit 0 232-1
long long int signed integer 64 bit -(263)-1 263-1
unsigned long long int unsigned integer 64 bit 0 264-1

### Basic Variable Data Type

Type Description Min Max
float single precision real 32 bit -1.175*10-38 3.402*1038
double double precision real 64 bit -2.25*10-308 1.797*10308
long double extended precision real 80 bit -3.362*10-4932 1.189*104932

### Basic Variable Data Type

Type Description Min Max
long double extended precision real 80 bit -3.362*10-4932 1.189*104932
﻿

## Variable Declaration syntax

### Variable Declaration Syntax


VariableType VariableName1[=Value1] [,VariableName2[=Value2],...VariableNameN[=ValueN]];


### Constant Variable Declaration Syntax


const VariableType VariableName1[=Value1];


### Example

/* Sum of Two Integers */
#include<stdio.h>
int main(void)
{
int a, b, c;
printf("Enter an Integer: ");
scanf("%d", &a);
printf("Enter another Integer: ");
scanf("%d", &b);
c = a + b;
printf("%d + %d = %d\n", a, b, c);
return 0;
}


scanf

int scanf(const char *format, ...);
scanf("%d", &a);
• Instructs the computer to perform an action
• Receives an integer from the screen
• f stands for formatedd
• Every statement must end with a semicolon, ; statment terminator

### Example

Enter an Integer: 3
Enter another Integer: 2
3 + 2 = 5


### Details

int a, b, c;//Definitions
a=10;//Declaration
b=14;//Declaration

• All Variables must be defined with a name and a data type before they can be used in C program
• Multiple variables of the same type in a single statement
• Case Sensitive
﻿

## Four Frequent Specifiers

### Examples: integer

int StudStrength;
printf("Enter the number of students in your course: ");
scanf("%d",&StudStrength);
printf("Number of Students in my course is %d\n",StudStrength);


### Examples: Float

float cost;
printf("Enter the cost of C Programming book: ");
scanf("%f",&cost);
printf("The cost of the C Programming book = %f\n",cost);


### Examples: Double

double cost;
printf("Enter the cost of C Programming book: ");
scanf("%lf",&cost);
printf("The cost of the C Programming book = %lf\n",cost);


### Examples: Characters/Strings

char CourseName[50];
char Enrolled;
printf("Have you Enrolled this course: ");
scanf("%c",&Enrolled);
printf("Enter the Course Name: ");
scanf("%s",CourseName);
printf("Enter the number of students in %s course: ",CourseName);


### Format Specifiers

Specifier Description For printf For scanf
%d Integer StudStrength &StudStrength
%f Float cost &cost
%lf double cost &cost
%c character Enrolled &Enrolled
%s string CourseName CourseName

### Other Specifiers

Specifier Description
%i Integer
%u unsigned decimal integer
%e or %E Scientific
%o octal

printf format type

%[flags][width][.precision][length]specifier

scanf format type

%[width][length]specifier

### Other Specifiers

Variable Type Format Specifier
%c char,signed char, unsigned char
%hi or %hd short int, signed short int
%hu unsigned short int
%d or %i int, signed int
%u unsigned int
%ld or %li long int,signed long int

### Other Specifiers

Variable Type Format Specifier
%lu unsigned long int
%lli or %lld long long int, signed long long int
%llu unsigned long long int

### Other Specifiers

Variable Type Format Specifier
%f, %F, %g, %G, %e, %E, %a, %A float
%lf, %lF, %lg, %lG, %le, %lE, %la, %lA double
%Lf, %LF, %Lg, %LG, %Le, %LE, %La, %LA long double

### Operator Precedence

Operators Operations Precedence
() Parentheses First
* Multiplication
/ Divison Second
% Remainder
- Subtraction
= Assignment Last

## Single Precision (Float)

### Decimal To Floating Point

• 2.625
• 210=102
• 0.62510=1012
• 2.62510=10.1012
• 2.62510=1.01012x21
• Mantissa : 0101 0000 0000 0000 0000 000
• Exponent : 1 + 127 = 128 = 1000 0000
• Sign bit: 0
• 0 1000 0000 0101 0000 0000 0000 0000 000

### Decimal To Floating Point

• -12.375
• 1210=11002
• 0.37510=0112
• 12.37510=1100.0112
• 12.37510=1.1000112x23
• Mantissa : 1000 1100 0000 0000 0000 000
• Exponent : 3 + 127 = 130 = 1000 0010
• Sign bit: 1
• 1 1000 0010 1000 1100 0000 0000 0000 000

﻿

## Decision Making

### if Statement

if (Expression)
{
//Code Block
}

• If the expression is true, inside the body of if is executed
• If the expression is false, inside the body of if is skipped from execution

### Examples: If

int n=5;
if(n%2==0)
{
printf("%d is even",n);
}


### if Statement

if (Expression)
{
//Code Block-1
}
else
{
//Code Block-2
}

• If the expression is true, inside the body of if is executed
• If the expression is false, inside the body of if is skipped from execution
• If the expression is false, else body of if is executed

### Examples: If...else

int n=5;
if(n%2==0)
{
printf("%d is even\n",n);
}
else
{
printf("%d is odd\n",n)
}


if (Expression-1)
{
//Code Block-1
}
else if (Expression-2)
{
//Code Block-2
}
else if (Expression-3)
{
//Code Block-3
}
....
else if (Expression-N)
{
//Code Block-N
}
else
{
//Code Block - (N+1)
}


• If the expression-1 is true, Code Block-1 is executed
• If the expression-2 is true, Code Block-2 is executed
• ...
• If the expression-N is true, Code Block-N is executed
• If all N-expressions are false, else block is executed

int x=2;
int y=3
if(x==y)
{
printf("%d Equal to %d\n",x,y);
}
else if(x > y)
{
printf("%d Greater than to %d\n",x,y);
}
else
{
printf("%d Less than to %d\n",x,y);
}


float a=4;
float b=5;
float c;
char op;
scanf("%c",&op);
if (op=='+')
{
c = a + b;
}
else if(op=='-')
{
c = a - b;
}
else if(op == '*')
{
c = a * b;
}
else if(op == '/')
{
c = a / b;
}
else
{
printf("Invalid Operator");
}


### Nested if Statement

if (Expression-1)
{
//Code Block-1
if (Expression-11)
{
//Code Block-11
}
else if (Expression-12)
{
//Code Block-12
}
...
else if (Expression-1N)
{
//Code Block-1N
}
else
{
//Code Block-1(N+1)
}
}
else if (Expression-2)
{
//Code Block-2
if (Expression-21)
{
//Code Block-21
}
else if (Expression-22)
{
//Code Block-22
}
...
else if (Expression-2N)
{
//Code Block-2N
}
else
{
//Code Block-2(N+1)
}
}
....
else if (Expression-M)
{
//Code Block-M
if (Expression-M1)
{
//Code Block-M1
}
else if (Expression-M2)
{
//Code Block-M2
}
...
else if (Expression-MN)
{
//Code Block-MN
}
else
{
//Code Block-M(N+1)
}
}
else
{
//Code Block-M+1
if (Expression-(M+1)1)
{
//Code Block-(M+1)1
}
else if (Expression-(M+1)2)
{
//Code Block-(M+1)2
}
...
else if (Expression-(M+1)N)
{
//Code Block-(M+1)N
}
else
{
//Code Block-(M+1)(N+1)
}
}


### Nested if Statement

• If the expression-1 is true, Code Block-1 is executed
• If the expression-1 is true and the expression-11 is true, Code Block-11 is executed
• If the expression-1 is true and the expression-12 is true, Code Block-12 is executed
• ...

### Nested if Statement

• If the expression-N is true, Code Block-N is executed
• If the expression-M is true and the expression-M1 is true, Code Block-M1 is executed
• If the expression-M is true and the expression-M2 is true, Code Block-M2 is executed
• If all M-expressions are false, else block is executed

int x=2;
int y=3
if(x>=y)
{
if(x==y)
{
printf("%d Equal to %d\n",x,y);
}
else
{
printf("%d Greater than  %d\n",x,y);
}
}
else
{
printf("%d Less than %d\n",x,y);
}


### Relational Operators

int x=2; int y=3;
Operator Description Example Result
> Greater than x>y False(0)
< Less than x < y True(1)
>= Greater than or equal to x>=y False(0)
<= Less than or equal to x<=y True(1)

### Relational Operators

int x=2; int y=3;
Operator Description Example Result
== Equal to x==y False(0)
!= Not Equal to x!=y True(1)

### Logical AND Operators (&&)

int x=2; int y=3; int z=4;
Example Result
x > y && x > z False(0)
x > y && x < z False(0)
x < y && x > z False(0)
x < y && x < z True(1)

### Logical OR Operators (||)

int x=2; int y=3; int z=4;
Example Result
x < y || x < z True(1)
x < y || x > z True(1)
x > y || x < z True(1)
x > y || x > z False(0)

### Logical NOT Operators (!)

int x=2; int y=3;
Example Result
!(x==y) True(1)
!(x < y) False(0)

### switch Statement

switch (n)
{
case constant1:
//Code Block-1
break;
case constant2:
//Code Block-2
break;
....
case constantN:
//Code Block-N
break;
default:
//Code Block - (N+1)
}


### Examples: switch Statement

float a=4;
float b=5;
float c;
char op;
scanf("%c",&op);
switch (op)
{
case '+':
c = a + b;
break;
case '-':
c = a - b;
break;
case '*':
c = a * b;
break;
case '/':
c = a / b;
break;
default:
printf("Invalid Operator");
}


### Selection Statements

• if - single-selection statement
• if...else - double-selection statement
• switch - multiple-selection statement

### Conditional Operator

• Ternary Operator
• Three operands
• Conditional expression
Syntax:
Expression ? TrueStatment: FalseStatement;
grade>=40 ? printf("Pass"): printf("Fail");
x>=y ? max=x: max=y;
x>=y && x>=z? max=x: (y>=x && y>=z ? max=y : max=z);

### Comma Operator

• binary Operator
• evaluates its first operand and discards the result
• evaluates the second operand and returns the result
int i = (5,7);//7 is assigned to i
int i = (5,7,4);//4 is assigned to i

### Comma Separator

• Variable Declarations
• Function Calls
• Enum declarations
int a=4,b=5,c=6;
int a=3,b=3,c=2;int i = (a,b,c);//2 is assigned to i
printf("%d %f %c", a,b,c);
scantf("%d %f %c", &a,&b,&c);
﻿

## Key words

### Key Words

 auto break case char signed const continue default do short double else enum extern sizeof float for goto if static int long register return struct switch typedef union unsigned void volatile while inline restrict _Bool

### Operators Associativity

Operators Associativity
() left to right
* / % left to right
+ - left to right
< <= > >= left to right
== != left to right
= right to left

### Express Evaluation

• z=pr mod q + w/x-y
• z = p * r % q + w / x - y
• z = a * (b + c) + c * (d + e)
• y = a * x * x + b * x + c
• average = a + b + c + d + e / 5

### Decimal To Floating Point

• -12.375
• 1210=11002
• 0.37510=0112
• 12.37510=1100.0112
• 12.37510=1.1000112x23
• Mantissa : 1000 1100 0000 0000 0000 000
• Exponent : 3 + 127 = 130 = 1000 0010
• Sign bit: 1
• 1 1000 0010 1000 1100 0000 0000 0000 000
﻿

## Structured Program

### Algorithm

• The solution to any computing problem involves executing a series of actions in a specific order
• A procedure for solving a problem in terms of
1. The actions to be executed
2. The order in which these actions are to be executed
• Specifying the order in which statements are to be executed in a computer program is called program control

### Pseudocode

• An artificial and informal language that helps you to develop algorithms
• Useful for developing algorithms that will be converted to structure programming
• Similar to Everyday English
• Not an actual computer programming language
• Can't be executed on computers
• Replace pseudo code statements with C equivalents

### Pseudocode

• Contains only action and decision statements
• Executed only when converted to C and run in C

### Control Structure

• Sequential Execution:Statments are executed one after another in the order in which they're written
• Transfer of control: got statement
• Sequence Structure
• Selection Structure
• Iteration Structure

### Flow Chart

• A graphical representation of an algorithm or a portion of an algorithm
• Rounded Rectangles (Start/End)
• Parallelogram (Input/Output)
• Rectangles (Process/action)
• Diamonds (Decision/Condition)
• Small Circles (Connector)
• Arrows or flow lines (to connect)

### Flow Chart

• Useful to develop and represent algorithms
• Shows how control strucutures operate
• Rectangles (Process)
• Diamonds (Selection/Condition)
• Small Circles (Connector)
• Arrows or flow lines (to connect)

### Errors

• Syntax Error: Compiler identifies
• Logic Error: Has its effect at execution time
• Fatal Logic Error: Causes a program to fail and terminate prematurely
• Nonfatal Logic Error: Allows a program to continue executing but to produce incorrect results

### Errors

• Fatal error: An attempt to divide by zero
• Infinite Loop: Never ending loop
﻿

## Iteration Structure

### Increment Operators

 ++ Increases the integer value by 1 x++ -- Decreases the integer value by 1 x--

### Bitwise Operators

a = 10; b = 15; a = 0000 1010, b = 0000 1111

 & Binary AND a & b 0000 1010 | Binary OR a | b 0000 1111 ^ Binary XOR a ^ b 0000 0101 ~ Binary OR ~a 1111 0101 << Binary Left Shift a << 2 0010 1000 >> Binary Right Shift a >> 2 0000 0010
x << y is x * 2y and x >> y is x /(2y)

### Assignment (Arithmetic) Operators

a = 10;

 = Simple Assignment a=10 += Add and Assigns a+=5 a = a + 5 15 -= Subtract and Assigns a-=5 a = a - 5 5 *= Multiply and Assigns a*=5 a = a * 5 50 /= Divide and Assigns a/=5 a = a / 5 2 %= Modulus and Assigns a%=5 a = a % 5 0

### Assignment (Bitwise Logic) Operators

a = 4; a = 0000 0100

 &= Binary AND and Assigns a&=2 a=a & 2; 0 |= Binary OR and Assigns a|=2 a = a | 2 6 ^= Binary XOR and Assigns a^=2 a = a ^ 2 6

### Assignment (Shift) Operators

a = 4; a = 0000 0100

 <<= Binary Left Shift and Assigns a<<=2 a = a << 2 16 >>= Binary Right shift and Assigns a>>=2 a = a >> 2 1

### for loop

for(initialization; condition; Update)
{
statement(s);
}

• Initialization: declare and initialize any loop variables. Executed once
• Condition: Evaluated at each step. True: body of the loop is executed. False: jumps out of the loop
• UpdateStatement: Evaluated at each step. Once the body of the loop is executed, loop variable is incremented or decremented or updated

### while loop

while(condition)
{
statement(s);
}

• Condition: Evaluated at each step. If condition is true, body of the loop is executed. Otherwise, it jumps out of the loop
• Entry controlled loop

### do...while loop

do
{
statement(s);
}while(condition);

• Body of the loop is executed at least once
• Condition: Evaluated at each step. If condition is true, body of the loop is executed. Otherwise, it jumps out of the loop
• Exit controlled loop

### Example

#include< stdio.h >
int main(void)
{
int n,sum;
printf("Enter the integer to get the sum of 1 to n: ");
scanf("%d",&n);
if (n<=0)
{
printf("Invalid Input\n");
return 0;
}
sum=0;
for(int i=1;i<=n;i++)
{
sum+=i;
}
printf("The sum first %d natural numbers  = %d\n",n,sum);
return 0;
}


### Example

#include< stdio.h >
int main()
{
int n;
int Prime;

printf("Enter an integer to find prime numbers between 1 to n: ");
scanf("%d", &n);

printf("Prime numbers between 1 to %d are:\n", n);

for(int i=2; i<=n; i++)
{
Prime = 1;
for(int j=2; j<=i/2; j++)
{
if(i%j==0)
{
Prime = 0;
break;
}
}

if(Prime==1)
{
printf("%d \t", i);
}
}
printf("\n");

return 0;
}


### Example

#include< stdio.h >
int main()
{
int n;
bool Prime;
int vote;
int cup=0,candle=0,pen=0,pencil=0,chalk=0;
printf("Enter the number of voters ");
scanf("%d", &n);

int i=0;
while(i< n)
{
printf("Voter %d: Enter one of the following number to Vote: \n",i+1);
printf("1. Cup\n");
printf("2. Candle\n");
printf("3. Chalk\n");
printf("4. Pen\n");
printf("5. Pencil\n");
scanf("%d",&vote);
switch(vote)
{
case 1:
cup++;
i++;
break;
case 2:
candle++;
i++;
break;
case 3:
chalk++;
i++;
break;
case 4:
pen++;
i++;
break;
case 5:
pencil++;
i++;
break;
default:
printf("Invalid Input, ReEnter\n");
}
}
printf("Number of Votes for Cup: %d\n",cup);
printf("Number of Votes for Candle: %d\n",candle);
printf("Number of Votes for Chalk: %d\n",chalk);
printf("Number of Votes for Pen: %d\n",pen);
printf("Number of Votes for Pencil: %d\n",pencil);
return 0;
}


### Example

#include< stdio.h >
#include< stdlib.h >
int main()
{
int n,s=0;
float num,sum=0,sum2=0;
printf("Enter the matrix dimension: ");
scanf("%d",&n);
if(n<=0)
{
printf("Invalid Input\n");
exit(0);
}
for(int i=0;i< n;++i)
{
for(int j=0;j< n;++j)
{
printf("Enter the a[%d][%d] :",i,j);
scanf("%f",&num);
s++;
sum2=sum2+num;
if(num< 0.0)
goto jump;
if(i==j)
continue;
if(i+j==n-1)
continue;
sum=sum+num;
}
}
printf("Required Sum = %f\n",sum);
jump:
float average=sum2/s;
printf("Average of the given input is %.4f\n",average);
return 0;
}


### Operators Associativity

Operators Associativity Type
++, -- left to right postfix
+,-,++, -- right to left prefix,unary
*, /, % left to right multiplicative
+, - left to right additive

### Operators Associativity

Operators Associativity Type
< , <=, >, >= left to right relational
== , != left to right equality
?: right to left conditional
=,+=,-=,*=,/=,%= right to left assignment

### Iterations

• Counter Controlled Iteration of definite iteration
• Sentinel-Controlled iteration or indefinite iteration

### while, do...while

Comparison while do...while
Controlling Condition appears at the start of the loop appears at the end of the loop
Iterations won't occur if the condition at the first iteration is false occurs at least once irrespective of the condition is true or false

### for and while

Comparison for while
Initalization, Conditions, iteration at the top of the loop before/top the loop, top of the loop, unnecessary
Number of Iterations known unknown
If no Condition infinite loop compilation error

### for and while

Comparison for while
Initalization Only once, never repeated can be done inside the loop
Iterations at the top or inside, preferably top inside the loop, can be with condition
﻿

## Functions

### Function

• A collection of statements grouped together to perform a specific task
• Allow you modularize the program
• All variables in function are local variables
• Divide code into separate functions logically

### Function

• Declaration: tells the compiler about its name, parameter (input) and return type
• Definition: Provides actual body
• Method, sub-routine, procedure
• Recursion: A function that calls itself is known as a recursive function

### Syntax

returnType functionName( input parameters )
{
statement(s);
}

• returnType is the data type of the value that function returns, can be void
• input parameters: can be empty, if non-empty, same number of arguments should be specified while calling.

### Examples

#include< stdio.h >
int smallest(int x, int y)
{
if(x< y)
{
return x;
}
else
{
return y;
}
}
int main(void)
{
int a,b;
printf("Enter two integers, let me tell your their relations\n");
printf("Enter the first integer: ");
scanf(" %d",&a);
printf("Enter the second integer: ");
scanf(" %d",&b);
int c=smallest(a,b);
printf("%d is the smallest between %d and %d\n",c,a,b);
return 0;
}


### Examples

#include < stdio.h>
{
int Prime = 1;
for(int j=2; j<=x/2; j++)
{
if(x%j==0)
{
Prime = 0;
break;
}
}

if(Prime==1)
{
printf("%d \t", x);
}
}
int main()
{
int n;
int Prime;

printf("Enter an integer to find prime numbers between 1 to n: ");
scanf("%d", &n);

printf("Prime numbers between 1 to %d are:\n", n);

for(int i=2; i<=n; i++)
{
}
printf("\n");
return 0;
}


### math.h

Function Description Example
sqrt(x) Square root of x sqrt(900.0)
cbrt(x) Cube root of x cbrt(8.0)
exp(x) exponential ex exp(3.0)
log(x) natural logarithm function log(3.0)

### math.h

Function Description Example
pow(x,y) x raised to power y xy pow(2,5)
fmod(x,y) remainder of x/y as a floating point fmod(13.657,2.333)
sin(x),cos(x),tan(x) trignometric functions in radians sin(0),cos(0),tan(0)

### math.h

Function Description Example
log10(x) logarithm of x log10(900.0)
fabs(x) absolute value of float fabs(-8.0)
ceil(x) smallest integer not less than x ceil(9.2)
floor(x) smallest integer not greater than x floor(8.5)

### Recursive Function

• Recursion: A function that calls itself is known as a recursive function

### Examples

#include < stdio.h>
int factorial(int x)
{
if(x>1)
{
x=x*factorial(x-1);
}
else
return 1;
}

int main()
{
int n;
printf("Enter an integer to find the factorial: ");
scanf("%d", &n);
int f;
if(n < 0)
{
printf("Factorial of Negative number is not possible\n");
return 0;
}
else if(n= =0)
{
f=1;
}
else
f=factorial(n);
printf("(%d)!=%d\n", n,f);
return 0;
}


### Pass by Value

• Copies the actual value of an argument into the formal parameter of the function
• Parameter modified inside the function, but has no effect on the argument

### Examples

#include< stdio.h >
void swap(int x, int y)
{
int temp=x;
x=y;
y=temp;
}
int main(void)
{
int a,b;
printf("Enter two integers\n");
scanf(" %d %d",&a,&b);
printf("a = %d b= %d\n",a,b);
swap(a,b);
printf("a = %d b= %d\n",a,b);
return 0;
}


### Pass by Reference

• Copies the address of an argument into the formal parameter of the function
• Parameter modified inside the function, affects value of the argument

### Examples

#include< stdio.h >
void swap(int *x, int *y)
{
int temp=x;
x=y;
y=temp;
}
int main(void)
{
int a,b;
printf("Enter two integers\n");
scanf(" %d %d",&a,&b);
printf("a = %d b= %d\n",a,b);
swap(&a,&b);
printf("a = %d b= %d\n",a,b);
return 0;
}

﻿

## Numerical Methods

Eigen Values/Vectors

### Eigen Values/Vectors

• Eigen vector is a non-zero vector. If T is a linear transformation from V to V and v is a non-zero vector of V, then v is said to be an eigen vector if T(v) is a scalar multiple of v
• The scalar multiple is called eigen value

## SVD

### Image Compression

• Hundreds of ways to Compress images, BTC, SVD,...
• 9MP gray scale image: 3000 x 3000 pixel
• For each pixel, we have same level of black and white
• 1 Pixel requires 1 byte storage
• For 9MP gray scale image ~ 8.6MB
• For 9MP RGB image ~ 25.8MB
• For 9MP CMYK image ~ 34.4MB

### Image/Video Compression

• For a HD TV, we need 1080 x 1920 pixels
• Most probably 24 frames per second
• Per Frame for RGB image, we need 5.94MB
• For 24 frames, we need 142.32MB

### SVD

• Any real or complex matrix $m \times n$ matrix A can be factorized as $A=U\Sigma V^*$
• U is an $m \times m$ Unitary Matrix
• V is an $n \times n$ Unitary Matrix
• $\Sigma \text{ is an } m \times n$ Matrix with non-negative real numbers
• $\Sigma$ entries are known as singular values

### SVD

• SVD: There are orthonormal bases (v's and u's for the row and colum spaces) such that $Av_i=\sigma_i u_i$ entries are known as singular values
• Use the unit eigenvectors of u (left singular vectors) of $AA^T$
• Use the unit eigenvectors of v (right singular vectors) of $A^TA$
• $\sigma's$ are singular value, square roots of the eigenvalues of $A^TA=AA^T$

### SVD

• $A^TA=V\Sigma U^*U\Sigma V^*=V\Sigma^2V^*$ $AA^T=U\Sigma V^*V\Sigma U^*=U\Sigma^2U^*$
• Both are spectral decompositions
• $\Sigma$ gives positive square roots of the eigenvalues of $A^TA$ We can re-arrange the decomposition such that $\sigma_1\geq\sigma_2\geq ... \geq\sigma_n$
• Spectral Theorem: If A is a symmetric matrix, then $A=Q\Sigma Q^T$ ,where U is an orthonormal matrix of eigen vectors and $\Sigma$ is a diagonal matirx of eigenvalues

### Image/Video Compression

• Send the vector U, $\Sigma$ ,V
• Send only few vectors that contribute most to the sum. It can reduce image quality, but reduces storage space.
• Let us send first k vectors and see the result

### Image/Video Compression

• For k=100, accurate production with 7.53% error
• For k=100, 40% of the original image size
• For 3000 x 3000 pixel, RGB image, it is enough to transmit 10.32MB
• For HD TV, RGB image, it is enough to transmit 56.92MB
﻿

## Graphical Method

### Graphical Method

• Simple Method
• An estimate to find the root of the equation $f(x)=0$
• Make a plot of the function
• Find when does it cross the x axis

﻿

## Bracketing Methods

### Bisection Method

#### Intermediate Value Theorem

• If $f$ is continuous on a closed interval $[x_l,x_u]$ and $c$ is any number between $f(x_l)$ and $f(x_u)$ then there is at least one number $x_r$ in the closed interval $[x_l,x_u]$ such that $f(x_r)=c$

#### Intermediate Value Theorem

• If $f$ is continuous on a closed interval $[x_l,x_u]$ and $f(x_l)f(x_u) < 0$ then there is at least one number $x_r$ in the closed interval $[x_l,x_u]$ such that $f(x_r)=0$

### Bisection Method

$a=x_l,b=x_u,c=x_r$

### Bisection Method

$a_1=x_l,b_1=x_u$

#### Bisection Algorithm

• Input: $x_l, x_u$ and $f$
• Output: root
1. Guess $x_l$ and $x_u$ for the root such that the $f(x_l)f(x_u) < 0$
2. Estimate the root: $x_r=\frac{x_l+x_u}{2}$
3. If $f(x_l)f(x_r) < 0$, the root lies in the lower subinterval. Set $x_l=x_r$ and return to Step 2
4. Else If $f(x_l)f(x_r) > 0$, the root lies in the lower subinterval. Set $x_u=x_r$ and return to Step 2
5. Else $f(x_l)f(x_r) = 0$, then $x_r$ is the root of the function

### Bisection Method

#### Parachutist

• $f(c)=\frac{gm}{c}\left(1-e^{-(c/m)t}\right)-v$
• $g=9.81 m/s^2, m=68.1kg,v=40 m/s, t=10s$
• $f(c)=\frac{668.06}{c}\left(1-e^{-0.146843c}\right)-40$
• $0=\frac{668.06}{c}\left(1-e^{-0.146843c}\right)-40$
• $1-\frac{40c}{668.06}=e^{-0.146843c}$
• $c=0,c=14.8011$
• Assume $x_l=12,x_r=16,\epsilon_a=10^-6,\epsilon_t=10^-5,M=1000$

### Bisection Algorithm Output

• $f(x)=6x^2-13x+6$
• Assume $x_l=0,x_r=1,\epsilon_a=10^-6,\epsilon_t=10^-5,M=1000$

﻿

## Bracketing Methods

### False position Method

#### False-Position Method

• Alternative to bisection method
• Drawback of bisection method: When dividing the interval $x_l$ and $x_r$ into equal halves, we don't worry about $f(x_l)$ and $f(x_r)$
• To overcome, this we join $f(x_l)$ and $f(x_r)$ by a straight line.

### False Position Method

#### False Position Algorithm

• Input: $x_l, x_u$ and $f$
• Output: root
1. Guess $x_l$ and $x_u$ for the root such that the $f(x_l)f(x_r) < 0$
2. Estimate the root: $x_r=x_u-\frac{(x_l-x_u)f(x_u)}{f(x_l)-f(x_u)}$
3. If $f(x_l)f(x_r) < 0$, the root lies in the lower subinterval. Set $x_l=x_r$ and return to Step 2
4. Else If $f(x_l)f(x_r) > 0$, the root lies in the lower subinterval. Set $x_u=x_r$ and return to Step 2
5. Else $f(x_l)f(x_r) = 0$, then $x_r$ is the root of the function

#### Modified False Position

• The draw back of false position method is its onsideness
• To overcome this drawback modified false position method implement the following strategy
• It counts the number of times the bounds stays in oneside
• If it stays at least two times, then the function value at this stagnant bound is halved
﻿

## Numerical Errors

#### Accuracy and Precision

• Accuarcy: It refers to how closely a computed or measured values agrees with the true value
• Precision: It refers to how closely computed or measured values agree with each other
• Inaccuracy or bias: Systmatic deviation from truth
• Imprecision or uncertainty: Refers to the magnitude of the scatter

### Accuracy and Precision

#### Errors

• True Error: $E_t=\text{true value - approximation}$
• True Relative Error $\epsilon_{rt} =\frac{\text{true value - approximation}}{\text{true value}}$
• True Percent Relative Error $\epsilon_{t} =\frac{\text{true value - approximation}}{\text{true value}}\times 100\%$
• Normalized approximat percent relative error $\epsilon_{a} =\frac{\text{current approximation - previous approximation}}{\text{current approximation}}\times 100\%$

#### Round off Error

• Round off error: The difference between an approximation of a number used in computation and its exact value.
• or The difference between the result produced by a given algorithm using exact arithmetic and the result produced by the same algorithm using finite-precision

#### Round off Error

• Computers can represent to a finite precision
• Most important for real numbers
• Machine dependent
• Result from using an approximate number to represent exact number
• Examples: $e,\pi,\sqrt{2},\sqrt{p}$
• Due to limited bits for storage

#### Floating Point Representation

• $m.b^e$
• m: mantissa, b: base, e: exponent
• $150.678=0.150678\times 10^3$
• $1/34=0.029411765... \approx 0.0294\times 10^0=0.2941\times 10^{-1}$
• Chopping
• $\frac{1}{b}\leq m < 1$
• If e is too large, overflow error: nan or -nan
• If e is too small, underflow error: simply set to 0

#### Truncation Error

• Method dependent
• Errors obtained from using an approximation rather than exact procedure
• Examples: Taylor Series

#### Big O, little o

Let $x_n \text{ and } \alpha_n$ be two different sequences, we write if there are constants C and r such that $|x_n| \leq C|\alpha_n|$, when $n\geq r$.

$\alpha_n\neq 0 \implies |\frac{x_n}{\alpha_n}|$ remains bounded by C as $n \rightarrow \infty$ That is

#### Big O, little o

Examples:

$\frac{n+1}{n} = O(\frac{1}{n})$

$\frac{1}{n ln n} = o(\frac{1}{n})$

$\frac{1}{n} = o(\frac{1}{ln n})$

$\frac{5}{n}+e^{-n} = O(\frac{1}{n})$

$e^{-n} = O(\frac{1}{n})$

Examples:

#### Order of Convergence

Let $x_0,x_1,x_2,...$ be a sequence which converges to TV. If there exists a number $p \text{ and a constant C}$ s.t.
• $p$ is called the order of convergence
• C is error constant
• Linear Convergence, if $C < 1 \text{ and } p = 1$ That is

#### Order of Convergence

• Super Linear, if $p > 1$, That is,
• Quadratic, if $p=2$

#### Order of Convergence for Bisection

$I_n=[a_n,b_n], |I_n|=b_n-a_n=2^{-n}(b_0-a_0)$

﻿

## Open Methods

### Fixed Point Iteration

• Root is located within an interval
• Although, this method converges always, it is not always possible to locate the lower and upper interval
• Slow convergence
• Not suitable to find multiple roots or function whose tangent is x-axis or function with significant curvature

### Open Methods

• Require one initial guess or two starting values
• It is not necessary that initial guesses should bracket the root
• It can diverge or move away from the true root
• Converge much more quickly than the bracketing methods

#### Fixed Point

A fixed point of a function is an element of the function's domain that is mapped to itself by the function

x is a fixed point of the function f, if f(x)=x

#### Fixed Point and continuous

Let $F:\mathbb{R}\rightarrow\mathbb{R}$ be a continuous function. Define a sequence $\{x_n\}$ in $\mathbb{R}$ by $x_{n+1}=F(x_n)$ and then

Therefore, $s$ is called a fixed point of the function $F$

#### Brouwer's fixed point theorem

Every continuous function from a closed disk to itself has at least one fixed point

#### Contractive Mapping

A function $F:[a,b]\rightarrow [a,b]$ is said to be contractive if there exists a number $\lambda < 1$ such that $|F(x)-F(y)|\leq \lambda |x-y|$ for all points $x,y\in [a,b]$

#### Contractive Mapping Theorem

Let $F:[a,b]\rightarrow [a,b]$ be a contractive mapping. Then $F$ has a unique fixed point. Moreover, this fixed point is the limit of every sequences obtained from $x_{n+1}=F(x_n)$ with any starting point $x_0 \in [a,b]$

#### Fixed Point Iteration

• Suppose $F$ is a given function and you would like to find the roots of the function $F$
• Then write $F(x)=0$
• Re-arrange the function in such a way that $g(x)=x$
• Simply you can add and subtract $x$ on both sides, that is $g(x)=F(x)+x$
• Now, finding the root of $F(x)$ is same as finding the fixed point $g(x)$

#### Fixed Point Iteration

• Define $x_{n+1}=g(x_n)$
• Then for given initial guess $x_0$, we obtain the fixed point of the function $g(x)$ and hence the root of the function $F$

#### Fixed Point Iteration Algorithm

• Input: $x_0, \epsilon$ and $f$
• Output: root
1. Convert $f$ to $g$
2. $x_r=x_0$
3. $x_r^{old}=x_r$
4. $x_r=g(x_r^{old})$
5. If $x_r \neq 0$, $\epsilon_a = |\frac{x_r-x_r^{old}}{x_r}|\times 100\%$
6. If $\epsilon_a > \epsilon$, then goto step 3

#### Order of Convergence for Fixed Point Iterations

$x_{n+1}=g(x_n)$ and $TV=g(TV)$

By MVT for some $\xi$ which is a point between $x_{n+1}$ and TV

for some $\xi$

#### Order of Convergence for Fixed Point Iterations

If $|g'(x)|< 1 \forall x$,then the error decreases.

Also

Therefore, p=1, C < 1 and linear convergent
﻿

## Open Methods

### Newton Raphson Method

#### Newton-Raphson Method

Most widely used method to find roots

x is a fixed point of the function f, if f(x)=x

#### Taylor Series

Let $f:\mathbb{R}\rightarrow\mathbb{R}$ be a continuous function and $f''$ exists and continuous, then $f(x)=f(a)+(x-a)f'(a)+O((x-a)^2).$

Suppose the root of $f$ is $x$ then

Let $a = x_n, x = x_{n+1}$ then $x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}, n \geq 0$

#### Newton-Raphson Algorithm

• Input: $x_0, \epsilon, \delta, M$ and $f$
• Output: root
1. $x_r=x_0$
2. For i=1,2,...,M
1. $x_r^{old}=x_r$
2. If $|f(x_r)|< \epsilon$, Stop
3. If $f'(x_r) \neq 0$ $x_r = x_r^{old} - \frac{f(x_r^{old})}{f'(x_r^{old})}$
4. If $x_r \neq 0$, $\epsilon_a = |\frac{x_r-x_r^{old}}{x_r}|\times 100\%$
5. If $\epsilon_a < \delta \text{ and } f(x_r) < \epsilon$, then stop

#### Order of Convergence for Newton-Rapshon

By Taylor's Theorem for some $\xi$ which is a point between $x_{n}$ and TV

﻿

## Open Methods

### Secant Method

#### Newton-Raphson Method

Difficult to find the derivatives for a few function

It can perform poorly

It can diverge from the root

#### Secant Method

In the Newton-Raphson method replace the derivative using backward finite difference method

#### Secant Method

It requires two initial estimates

#### Secant Algorithm

• Input: $x_0, x_1, \epsilon, \delta, M$ and $f$
• Output: root
1. For i=1,2,...,M
1. If $|f(x_0)|< \epsilon \text{ or }|f(x_1)|< \epsilon$, Stop
2. If $|f(x_1)-f(x_0)| \neq 0$ $x_2 = x_1 - \frac{f(x_1)(x_0-x_1)}{f(x_0)-f(x_1)}$
3. If $x_2 \neq 0$, $\epsilon_a = |\frac{x_2-x_1}{x_2}|\times 100\%$
4. $x_0 = x_1, x_1=x_2$
5. If $\epsilon_a < \delta \text{ and } |f(x_1)| < \epsilon$, then stop

#### Modified Secant Method

It requires only one initial estimate

﻿

### Muller's Method for Roots of Polynomials

#### Muller's Method

Secant method obtains a root estimate by projecting a straight line to the x-axis through function values

Muller's method takes a similar approach but projects a parabola through three points

#### Muller's Method

Let us find a parabola equation joining three points $(x_0,f(x_0)),(x_1,f(x_1)) \text{ and }(x_2,f(x_2))$

Consider the following parabola

At given three points

#### Muller's Method

Let

Then on simplification, we get

#### Muller's Algorithm

• Input: $x_0, x_1, x_2, \epsilon, M$ and $f$
• Output: root
1. For i=1,2,...,M
1. $h_0 = x_1-x_0, h_1 =x_2-x_1$, $d_0 = \frac{f(x_1)-f(x_0)}{h_0}, d_1 =\frac{f(x_2)-f(x_1)}{h_1}$
2. $a=\frac{d_1-d_0}{h_1+h_0}, b=ah_1+d_1, c=f(x_2), D=\sqrt{b^2-4ac}$
3. If $\frac{|b+D|}{|b-D|}>1$, then $den=b+D$ Else $den=b-D$
4. $x_r=x_2+\frac{-2c}{den}$, $\epsilon_a = |\frac{x_3-x_2}{x_3}|\times 100\%$
5. If $\epsilon_a < \delta \text{ or } f(x_r) < \epsilon$, Stop.
6. Else $x_0 = x_1, x_1=x_2, x_2 = x_r$
﻿

## CPU Cache

#### CPU Cache

• A CPU cache is a smaller faster memory used by the CPU of a computer to reduce the average time to access memory
• L1 Cache - Level 1 Cache - 2KB - 64 KB
• L2 Cache - Level 2 Cache - 256KB - 512 KB
• L3 Cache - Level 3 Cache - 1MB - 8 MB

#### L1 Cache

• Instructions are first searched in this cache
• Very small in size. Faster than the rest

#### L2 Cache

• If the instructions are not present in the L1 cache then it looks in the L2 Cache
• It is bigger in size than L1, slower than L1, but faster than L3

#### L3 Cache

• If the instructions are not present in the L1 and L2 cache then it looks in the L3 Cache
• It is bigger in size than L1 and L2, slower than L1 and L2, but faster than RAM

﻿

## Arrays

#### Arrays

• An array is a group of contiguous memory locations that all have same data type.
• To refer a particular location or element in the array specity the array's name and the position number of the particular element in the array
• Firs Element in every arrays is the zeroth element

#### Arrays

• Any one of the elements may be referred to by giving the array's name followed by the position number of the particular element in square brackets []
• The position number in the square bracket is called the element's index or subscript

#### Types

• One Dimensional Arrays
• Multidimensional Arrays

#### 1D Arrays

VariableType ArrayName[N1];
• A structured collection of components or often called array elements
• Must be declared before usage
• Example: Vectors
• Number of Elements = N1

#### 1D Arrays

• Initializing Arrays
• Accessing Array elements

#### 2D Arrays

VariableType ArrayName[N1][N2];
• Array of arrays
• Require two indices
• Example: Matrices
• Number of Elements = N1*N2

#### 2D Arrays

• Initializing Arrays
• Accessing Array elements

#### Multidimensional Arrays

VariableType ArrayName[N1][N2]...[Nm];
• Require multi indices
• Number of Elements N1*N2*..*Nm

## 1DArray.C

#include<stdio.h> //header file
int main(void)
{
int n[5]={2,3,4,5,8};
for(int i=0;i< 5;i++)
{
printf("n[%d]=%d\n",i,n[i]);
}
return 0;
}


## 1DArrayEx.C

#include<stdio.h> //header file
#define SIZE 100
int main(void)
{
int n[10]={0};
int s[]={1,3,4,56,78,34};
int t[SIZE];
for(int i=0;i < SIZE;i++)
{
t[i]=2*i;
}
//Codes here
return 0;
}


#### Preprocessor directive

• #define SIZE 100
• It defines symbolic constant SIZE whose value is 100
• A symbolic constant is an identifier that is replaced with replacement text by the C preprocessor before the program is compiled

#### Arrays and Function

• To pass an array argument to a function, specify the arrays name without brackets
#include<stdio.h> //header file
#define VECSIZE 100
double dotproduct(const double vectorA[],const double vectorB[])
{
double sum=0;
for(int i=0;i < VECSIZE;i++)
{
sum+=vectorA[i]*vectorB[i];
}
return sum;
}
int main(void)
{
double vec_A[VECSIZE];
double vec_B[VECSIZE];
for(int i=0;i < VECSIZE;i++)
{
vec_A[i]=100-i*i;
vec_B[i]=300-i*i;
}
printf("A.B=%lf\n",dotproduct(vec_A,vec_B));
return 0;
}

﻿

## Pointers

#### Pointers

• A Variable whose value is the address of another variable
• Direct access of memory location
• Must declare before you can use it to store any variable address
• Allows us to indirectly access variables, that is, talk about its address rather than its value

#### Pointers

• Understanding of pointers and your ability to use separate you from novice programmer to experienced one
• The basic concept is simple: variable that stores the address of a memory location
• However, complicated when we start applying pointer operators and discern their cryptic notations

#### Pointers-Syntax

VariableType *PtrVariable;
• * indicates variable is a pointer
• Pointers can be defined to point to objects of any type

#### Pointers-Declaration

int y=5;
int *yPtr;
yPtr=&y; 
• Caution: Each pointer must be declared with * prefixed to the name

#### Pointers-Initialization

• Should be initialized when they are defined or they can be assigned a value
• A pointer may be initialized to NULL, 0 or an address
• NULL - A symbolic constant
• Initializing to 0 is equivalent to initializing NULL

#### Pointers And Memory

Global The entire file The lifetime of the application
Static The function where it is declared within The lifetime of the application
Automatic/local The function where it is declared within While the function is executing
Dynamic Determined by the pointers that reference this memory Until the memory is freed

#### Why Pointers

• Creating fast and efficient code
• Providing a convenient means for addressing many types of problems
• Supporting dynamic memory allocation
• Making expressions compact and succinct
• Providing the ability to pass data structures by pointer without incurring a large overhead
• Protecting data passed as a parameter to a function

#### Problems with Pointers

Although Pointer is a powerful tool, the following problems can occur
• Accessing arrays and other data structures beyond their bounds
• Reference local variables after they have gone out of existence
• Referencing heap allocated memory after it has been released
• Dereferencing a pointer before memory has been allocated to it

• Unary Operator
• Returns address of its operand
int y=5;
int *yPtr;
yPtr=&y;
• The last statement assigns the address of the variable y to pointer variable yPtr.
• yPtr is said to be point to y

• The operand of the address operator must be a variable
• The address operator can't be applied to constants or expression

### Indirection (*) Operator

• Unary operator
• Indirection or Dereferencing operator
• Returns the value of the object to which its operand points
printf("%d", *yPtr);
prints the value of the variable y(5).

Caution: Fatal Execution Error: Dereferencing a pointer that has not been properly initialized or that has not been assigned to point to a specific location in memory is an error.

### Operators Associativity

Operators Associativity Type
[], (), ++(postfix), --(postfix) left to right postfix
+,-,++, --, !, *, & right to left prefix,unary
*, /, % left to right multiplicative
+, - left to right additive

### Operators Associativity

Operators Associativity Type
< , <=, >, >= left to right relational
== , != left to right equality
&& left to right logical AND
|| left to right logical OR

### Operators Associativity

Operators Associativity Type
?: right to left conditional
=,+=,-=,*=,/=,%= right to left assignment
, left to right comma

## Passing Arguments and Pointers

• Pass by value
• Pass by reference

## Pass by Value

#include<stdio.h> //header file
int Square(int n)
{
return n*n;
}

int main(void)
{
int num=5;
printf("Square of %d is %d\n",num,Square(num));
return 0;
}


## Pass by Reference

#include<stdio.h> //header file
void Square(int *numPtr)
{
*numPtr = *numPtr * *numPtr;
}
int main(void)
{
int num=5;
Square(&num);
printf("Square of %d is %d\n",num,Square(num));
return 0;
}


## Pass by Reference

• Address of the number is passed to function Square
• Function takes as a parameter pointer to an integer, numPtr
• The function dereferences the pointer and squares the value to which the numPtr points
• Assigns the result to *numPtr
• The *numPtr is same as num in main
• Changes the value of num in main

## Pass by Reference

Caution: Use pass-by-value to pass arguments to a function, unless the caller explicity requires the called function to modify the value of the argument variable in the caller's environment. This prevents accidental modification of the caller's arguments and is another example of the principle of least privilege.

﻿

## Numerical Linear Algebra

#### Linear System

• Linear System has a plenty of applications
• Artificial Intelligence, Machine Learning
• Spring System, Electrical Circuits
• All Engineering Disciplines and so on

#### Diagonal System

• When the linear system is diagonal( $Dx=b$), it is easy to solve
$D=\begin{pmatrix} d_{11} & 0 & 0 & \cdots & 0\\ 0 & d_{22} & 0 & \cdots & 0\\ \vdots & \vdots & \vdots & \cdots & \vdots\\ 0 & 0 & 0 & \cdots & d_{nn} \\ \end{pmatrix}$ $x=\begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix}$ and $b=\begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_n \end{pmatrix}$

The solution is $x=\begin{pmatrix} \frac{b_1}{d_{11}} \\ \frac{b_2}{d_{12}} \\ \vdots \\ \frac{b_n}{d_{nn}} \end{pmatrix}$

#### Upper Triangular System

• When the linear system is an Upper Triangular system( $Ux=y$), we can move from the backward direction to find the solution.
$U=\begin{pmatrix} u_{11} & u_{12} & u_{13} & \cdots & u_{1n}\\ 0 & u_{22} & u_{23} & \cdots & u_{2n}\\ \vdots & \vdots & \vdots & \cdots & \vdots\\ 0 & 0 & 0 & \cdots & u_{nn} \\ \end{pmatrix}$ $x=\begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix}$ and $y=\begin{pmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{pmatrix}$

The solution is

#### Backward Substitution Algorithm

• Input: $U, y$ and
• Output: $x$

1. $x_n=\frac{y_n}{u_{nn}}$
2. $\text{for } i=1,2,...,n-1$

#### Lower Triangular System

• When the linear system is a lower Triangular system( $Ly=b$), we can move from the forward direction to find the solution.
$L=\begin{pmatrix} l_{11} & 0 & 0 & \cdots & 0\\ l_{21} & l_{22} & 0 & \cdots & 0\\ \vdots & \vdots & \vdots & \cdots & \vdots\\ l_{n1} & l_{n2} & l_{n3} & \cdots & l_{nn} \\ \end{pmatrix}$ $y=\begin{pmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{pmatrix}$ and $b=\begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_n \end{pmatrix}$

The solution is

#### Forward Substitution Algorithm

• Input: $L, b$ and
• $y$ and

1. $y_1=\frac{b_1}{l_{11}}$
2. $\text{for } i=2,3,...,n$

﻿

#### Gauss Elimination

• It is a method to solve a linear system $Ax=b$
• Using elementary row operations, we reduce the system to upper triangular form
• Using Forward Substitution, we can solve the system

#### Gauss Elimination

$A=\begin{pmatrix} a_{11} & a_{12} & a_{13} & \cdots & a_{1n}\\ a_{21} & a_{22} & a_{23} & \cdots & a_{2n}\\ a_{31} & a_{32} & a_{33} & \cdots & a_{3n}\\ \vdots & \vdots & \vdots & \cdots & \vdots\\ a_{n1} & a_{n2} & a_{n3} & \cdots & a_{nn} \\ \end{pmatrix}$ $\begin{pmatrix} x_1 \\ x_2 \\ x_3\\ \vdots \\ x_n \end{pmatrix}$ = $\begin{pmatrix} b_1 \\ b_2 \\ b_3 \\ \vdots \\ b_n \end{pmatrix}$

$A=\begin{pmatrix} 1 & \frac{a_{12}}{a_{11}} & \frac{a_{13}}{a_{11}} & \cdots & \frac{a_{1n}}{a_{11}}\\ a_{21} & a_{22} & a_{23} & \cdots & a_{2n}\\ a_{31} & a_{32} & a_{33} & \cdots & a_{3n}\\ \vdots & \vdots & \vdots & \cdots & \vdots\\ a_{n1} & a_{n2} & a_{n3} & \cdots & a_{nn} \\ \end{pmatrix}$, $b=\begin{pmatrix} \frac{b_1}{a_{11}} \\ b_2 \\ b_3 \\ \vdots \\ b_n \end{pmatrix}$

$A=\begin{pmatrix} 1 & \frac{a_{12}}{a_{11}} & \frac{a_{13}}{a_{11}} & \cdots & \frac{a_{1n}}{a_{11}}\\ 0 & a_{22}-\frac{a_{12}a_{21}}{a_{11}} & a_{23}-\frac{a_{13}a_{21}}{a_{11}} & \cdots & a_{2n}-\frac{a_{1n}a_{21}}{a_{11}}\\ 0 & a_{32}-\frac{a_{12}a_{31}}{a_{11}} & a_{33}-\frac{a_{13}a_{31}}{a_{11}} & \cdots & a_{3n}-\frac{a_{1n}a_{31}}{a_{11}}\\ \vdots & \vdots & \vdots & \cdots & \vdots\\ 0 & a_{n2}-\frac{a_{12}a_{n1}}{a_{11}} & a_{n3}-\frac{a_{13}a_{n1}}{a_{11}} & \cdots & a_{nn}-\frac{a_{1n}a_{n1}}{a_{11}}\\ \end{pmatrix}$, $b=\begin{pmatrix} \frac{b_1}{a_{11}} \\ b_2-\frac{b_1a_{21}}{a_{11}} \\ b_3-\frac{b_1a_{31}}{a_{11}} \\ \vdots \\ b_n-\frac{b_1a_{n1}}{a_{11}} \end{pmatrix}$

#### Gauss Elimination

$A=\begin{pmatrix} 1 & \frac{a_{12}}{a_{11}} & \frac{a_{13}}{a_{11}} & \cdots & \frac{a_{1n}}{a_{11}}\\ 0 & a_{22}' & a_{23}' & \cdots & a_{2n}'\\ 0 & a_{32}' & a_{33} & \cdots & a_{3n}'\\ \vdots & \vdots & \vdots & \cdots & \vdots\\ 0 & a_{n2}' & a_{n3}' & \cdots & a_{nn}' \\ \end{pmatrix}$, $b=\begin{pmatrix} \frac{b_1}{a_{11}} \\ b_2' \\ b_3' \\ \vdots \\ b_n' \end{pmatrix}$ $a_{ij}'=a_{ij}-\frac{a_{1j}a_{j1}}{a_{11}}, b_j'=b_j-\frac{b_1a_{j1}}{a_{11}}, i,j=2,3,4,...,n$

$A=\begin{pmatrix} 1 & \frac{a_{12}}{a_{11}} & \frac{a_{13}}{a_{11}} & \cdots & \frac{a_{1n}}{a_{11}}\\ 0 & 1 & \frac{a_{23}'}{a_{22}'} & \cdots & \frac{a_{2n}'}{a_{22}'}\\ 0 & a_{32}' & a_{33} & \cdots & a_{3n}'\\ \vdots & \vdots & \vdots & \cdots & \vdots\\ 0 & a_{n2}' & a_{n3}' & \cdots & a_{nn}' \\ \end{pmatrix}$, $b=\begin{pmatrix} \frac{b_1}{a_{11}} \\ \frac{b_2'}{a_{22}'} \\ b_3' \\ \vdots \\ b_n' \end{pmatrix}$

$A=\begin{pmatrix} 1 & \frac{a_{12}}{a_{11}} & \frac{a_{13}}{a_{11}} & \cdots & \frac{a_{1n}}{a_{11}}\\ 0 & 1 & \frac{a_{23}'}{a_{22}'} & \cdots & \frac{a_{2n}'}{a_{22}'}\\ 0 & 0 & a_{33}'-\frac{a_{23}'a_{32}'}{a_{22}'} & \cdots & a_{3n}'-\frac{a_{2n}'a_{32}'}{a_{22}'}\\ \vdots & \vdots & \vdots & \cdots & \vdots\\ 0 & 0 & a_{n3}'-\frac{a_{23}'a_{n2}'}{a_{22}'} & \cdots & a_{nn}'-\frac{a_{2n}a_{n3}'}{a_{22}'}\\ \end{pmatrix}$, $b=\begin{pmatrix} \frac{b_1}{a_{11}} \\ \frac{b_2'}{a_{22}'} \\ b_3'- \frac{b_2'a_{32}'}{a_{22}'} \\ \vdots \\ b_n'-\frac{b_2'a_{n2}'}{a_{22}'} \end{pmatrix}$

#### Gauss Elimination

$A=\begin{pmatrix} 1 & \frac{a_{12}}{a_{11}} & \frac{a_{13}}{a_{11}} & \cdots & \frac{a_{1n}}{a_{11}}\\ 0 & 1 & \frac{a_{23}'}{a_{22}'} & \cdots & \frac{a_{2n}'}{a_{22}'}\\ 0 & 0 & a_{33}^{''} & \cdots & a_{3n}^{''}\\ \vdots & \vdots & \vdots & \cdots & \vdots\\ 0 & 0 & a_{n3}^{''} & \cdots & a_{nn}^{''} \\ \end{pmatrix}$, $b=\begin{pmatrix} \frac{b_1}{a_{11}} \\ b_2' \\ b_3^{''} \\ \vdots \\ b_n^{''} \end{pmatrix}$ $a_{ij}^{''}=a_{ij}'-\frac{a_{2j}'a_{j2}'}{a_{22}'}, b_j^{''}=b_j'-\frac{b_2a_{j2}'}{a_{22}'}, i,j=3,4,...,n$

On Repeating the procedure $A=\begin{pmatrix} 1 & \frac{a_{12}}{a_{11}} & \frac{a_{13}}{a_{11}} & \cdots & \frac{a_{1n}}{a_{11}}\\ 0 & 1 & \frac{a_{23}'}{a_{22}'} & \cdots & \frac{a_{2n}'}{a_{22}'}\\ 0 & 0 & 1 & \cdots & \frac{a_{3n}^{''}}{a_{33}{''}}\\ \vdots & \vdots & \vdots & \cdots & \vdots\\ 0 & 0 & 0 & \cdots & 1 \\ \end{pmatrix}$, $b=\begin{pmatrix} \frac{b_1}{a_{11}} \\ b_2' \\ b_3^{''} \\ \vdots \\ \frac{b_n^{(n-2)}}{a_{nn}^{n-2}} \end{pmatrix}$

Using Backward substitution we can solve this problem to find the solution.

#### Gauss Elimination Algorithm

• Input: $A,b$
• Output: $x$

1. Initialization
2. $\text{for } k=1 \text{ to } n-1$
3. $~~~~~\text{for } i=k+1 \text{ to } n$
4. $~~~~~~~~factor=\frac{a_{ik}}{a_{kk}}$
5. $~~~~~~~~\text{for } j=k+1 \text{ to } n$
6. $~~~~~~~~~~~~a_{ij}=a_{ij}-factor*a_{kj}$
7. $~~~~~~~~b_i=b_i-factor*b_k$
8. $x_n=\frac{b_n}{a_{nn}}$
9. $\text{for } i=n-1 \text{ to } 1$
10. $~~~~sum=b_i$
11. $~~~~\text{for } j=i+1 \text{ to } n$
12. $~~~~~~~~sum = sum - a_{ij}*x_j$
13. $~~~~x_i=\frac{sum}{a_{ii}}$
﻿

## LU Decomposition

#### LU Decomposition

• We know that it is easy to solve diagonal system $Dx=b$
• We know that it is easy to solve upper triangular system $Ux=y$ using backward substitution
• We know that it is easy to solve lower triangular system $Ly=b$ using forward substitution
• If we can decompose the system $Ax=b$ as follows $LUx=b$, then we can solve it in the following manner $L(Ux)=b \implies Ly = b, Ux=y$
• Therefore, first we can solve $Ly=b$ using forward substitution and then $Ux=y$ using backward substitution

#### LU Decomposition

$A=\begin{pmatrix} a_{11} & a_{12} & a_{13} & \cdots & a_{1n}\\ a_{21} & a_{22} & a_{23} & \cdots & a_{2n}\\ \vdots & \vdots & \vdots & \cdots & \vdots\\ a_{n1} & a_{n2} & a_{n3} & \cdots & a_{nn} \\ \end{pmatrix}$ $=\begin{pmatrix} l_{11} & 0 & 0 & \cdots & 0\\ l_{21} & l_{22} & 0 & \cdots & 0\\ \vdots & \vdots & \vdots & \cdots & \vdots\\ l_{n1} & l_{n2} & l_{n3} & \cdots & l_{nn} \\ \end{pmatrix}$ $\begin{pmatrix} u_{11} & u_{12} & u_{13} & \cdots & u_{1n}\\ 0 & u_{22} & u_{23} & \cdots & u_{2n}\\ \vdots & \vdots & \vdots & \cdots & \vdots\\ 0 & 0 & 0 & \cdots & u_{nn} \\ \end{pmatrix}$

It is not necessary that we get an unique LU decomposition. We can select $l_{ii}=1$ or $u_{ii}=1$ or $l_{ii}=a_{ii}$ or $u_{ii}=a_{ii}$ or we can select any non-zero values, that is $l_{ii} \neq 0$ or $u_{ii} \neq 0$

#### LU Decomposition Algorithm

• Input: $A$
• Output: $L, U$

1. Initialization
2. $\text{for } k=1 \text{ to } n$
3. $~~~~~~sum=0$
4. $~~~~~\text{for } s=1 \text{ to } k-1$
5. $~~~~~~~~sum=sum+l_{ks}u_{sk}$
6. $~~~~\text{Choose a non-zero for } l_{kk} \text{ or } u_{kk}, \text{ compute other from } l_{kk}u_{kk}=a_{kk}-sum$
7. $~~~~~\text{for } j=k+1 \text{ to } n$
8. $~~~~~~~~~~~sum=0$
9. $~~~~~~~~~~~~\text{for } s=1 \text{ to } k-1$
10. $~~~~~~~~~~~~~~~~~~sum=sum+l_{ks}u_{sj}$
11. $~~~~~~~~~~~~u_{kj}=(a_{kj}-sum)/l_{kk}$
12. $~~~~~\text{for } i=k+1 \text{ to } n$
13. $~~~~~~~~~~sum=0$
14. $~~~~~~~~~~~~\text{for } s=1 \text{ to } k-1$
15. $~~~~~~~~~~~~~~~~~~sum=sum+l_{is}u_{sk}$
16. $~~~~~~~~~~~~l_{ik}=(a_{ik}-sum)/u_{kk}$

#### Doolittle Decomposition Algorithm

Here we assume that, unit upper triangular system, that is, $u_{kk}=1$

• Input: $A$
• Output: $L, U$

1. Initialization
2. $\text{for } k=1 \text{ to } n$
3. $~~~~l_{kk}=1$
4. $~~~~~\text{for } j=k \text{ to } n$
5. $~~~~~~~~~sum=0$
6. $~~~~~~~~~~\text{for } s=1 \text{ to } k-1$
7. $~~~~~~~~~~~~~~~~~~sum=sum+l_{ks}u_{sj}$
8. $~~~~~~~~~~u_{kj}=(a_{kj}-sum)$
9. $~~~~~\text{for } i=k+1 \text{ to } n$
10. $~~~~~~~~~sum=0$
11. $~~~~~~~~~~\text{for } s=1 \text{ to } k-1$
12. $~~~~~~~~~~~~~~~~~~sum=sum+l_{is}u_{sk}$
13. $~~~~~~~~~~l_{ik}=(a_{ik}-sum)/u_{kk}$

#### Crout Decomposition Algorithm

Here we assume that, unit lower triangular system, that is, $l_{kk}=1$

• Input: $A$
• Output: $L, U$

1. Initialization
2. $\text{for } k=1 \text{ to } n$
3. $~~~~u_{kk}=1$
4. $~~~~~\text{for } i=k \text{ to } n$
5. $~~~~~~~~~sum=0$
6. $~~~~~~~~~~\text{for } s=1 \text{ to } k-1$
7. $~~~~~~~~~~~~~~~~~~sum=sum+l_{is}u_{sk}$
8. $~~~~~~~~~~l_{ik}=(a_{ik}-sum)$
9. $~~~~~\text{for } j=k+1 \text{ to } n$
10. $~~~~~~~~~sum=0$
11. $~~~~~~~~~~\text{for } s=1 \text{ to } k-1$
12. $~~~~~~~~~~~~~~~~~~sum=sum+l_{ks}u_{sj}$
13. $~~~~~~~~~~u_{kj}=(a_{kj}-sum)/l_{kk}$

#### Cholesky Decomposition Algorithm

Here we assume that $A$ is symmetric, therefore, we get $A = LL^T$

• Input: $A$
• Output: $L$

1. Initialization, Check Symmetri Matrix
2. $\text{for } k=1 \text{ to } n$
3. $~~~~~~~~~sum=0$
4. $~~~~~~~~~~\text{for } s=1 \text{ to } k-1$
5. $~~~~~~~~~~~~~~~~~~sum=sum+l_{ks}l_{ks}$
6. $~~~~~~~~~~l_{kk}=\sqrt{a_{ik}-sum}$
7. $~~~~~\text{for } i=k+1 \text{ to } n$
8. $~~~~~~~~~sum=0$
9. $~~~~~~~~~~\text{for } s=1 \text{ to } k-1$
10. $~~~~~~~~~~~~~~~~~~sum=sum+l_{is}l_{ks}$
11. $~~~~~~~~~~l_{ik}=(a_{ik}-sum)/l_{kk}$
﻿

## Operation Counting

#### Operation Counting

• When an algorithm is developed, we should discuss the complexity and the number of floating point operations involved in the process
• Let us revisit Gauss Elimination method with a $4 \times 4$ matrix and generalize it for $n$

#### Gauss Elimination

$A=\begin{pmatrix} a_{11} & a_{12} & a_{13} & a_{14}\\ a_{21} & a_{22} & a_{23} & a_{24}\\ a_{31} & a_{32} & a_{33} & a_{34}\\ a_{41} & a_{42} & a_{43} & a_{44} \\ \end{pmatrix}$ $\begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix}$ = $\begin{pmatrix} b_1 \\ b_2 \\ b_3 \\ b_4 \end{pmatrix}$

$A=\begin{pmatrix} 1 & \frac{a_{12}}{a_{11}} & \frac{a_{13}}{a_{11}} & \frac{a_{14}}{a_{11}}\\ a_{21} & a_{22} & a_{23} & a_{24}\\ a_{31} & a_{32} & a_{33} & a_{34}\\ a_{41} & a_{42} & a_{43} & a_{44} \\ \end{pmatrix}$, $b=\begin{pmatrix} \frac{b_1}{a_{11}} \\ b_2 \\ b_3 \\ b_4 \end{pmatrix}$

• We have done, 4 divisions on the $4 \times 4$ matrix
• Therefore, in case of d $n \times n$ matrix, we have $n$ division (floating point operations).
• Similarly for computing the RHS, we have one division
• Therefore we have $n+1$ operations

#### Gauss Elimination

$A=\begin{pmatrix} 1 & \frac{a_{12}}{a_{11}} & \frac{a_{13}}{a_{11}} & \frac{a_{14}}{a_{11}}\\ 0 & a_{22}-\frac{a_{12}a_{21}}{a_{11}} & a_{23}-\frac{a_{13}a_{21}}{a_{11}} & a_{24}-\frac{a_{14}a_{21}}{a_{11}}\\ 0 & a_{32}-\frac{a_{12}a_{31}}{a_{11}} & a_{33}-\frac{a_{13}a_{31}}{a_{11}} & a_{34}-\frac{a_{14}a_{31}}{a_{11}}\\ 0 & a_{42}-\frac{a_{12}a_{41}}{a_{11}} & a_{43}-\frac{a_{13}a_{41}}{a_{11}} & a_{44}-\frac{a_{14}a_{41}}{a_{11}}\\ \end{pmatrix}$, $b=\begin{pmatrix} \frac{b_1}{a_{11}} \\ b_2-\frac{b_1a_{21}}{a_{11}} \\ b_3-\frac{b_1a_{31}}{a_{11}} \\ b_4-\frac{b_1a_{41}}{a_{11}} \end{pmatrix}$

• For each $i^{th}$ row, we have to multiply by $a_{i1}$ and subtract.
• Therefore, we require 4 operations for each row to multiply and four operations to subtract. Hence, $2\times 4$ operations per row is required.
• For each row of the RHS, we require 2 operations.
• We should perform above operations for each of the 3 rows. So, finally, we require $3 \times 2 \times 4 + 3 \times 2$ operations for matrix.
• In terms of $n \times n$ matrix, we require $(n- 1) \times 2$ operations per row for RHS and $(n-1) \times 2 \times n$ operations for LHS
• Therefore, we require, $(n-1) \times 2 \times n + (n-1) \times 2$ operations.

#### Gauss Elimination

$A=\begin{pmatrix} 1 & \frac{a_{12}}{a_{11}} & \frac{a_{13}}{a_{11}} & \frac{a_{14}}{a_{11}}\\ 0 & \color{red}{a_{22}'} & \color{red}{a_{23}'} & \color{red}{a_{24}'}\\ 0 & \color{red}{a_{32}'} & \color{red}{a_{33}'} & \color{red}{a_{34}'}\\ 0 & \color{red}{a_{42}'} & \color{red}{a_{43}'} & \color{red}{a_{44}'}\\ \end{pmatrix}$, $b=\begin{pmatrix} \frac{b_1}{a_{11}} \\ \color{red}{b_2'} \\ \color{red}{b_3'} \\ \color{red}{b_4'} \end{pmatrix}$

• To reduce the system to the above form, we require $3 \times 2 \times 4 + 3 \times 2 + 5$ operations.
• Therefore, we require, $(n-1) \times 2 \times n + (n-1) \times 2 + n+1$ operations for $n \times n$ system.
• If we concentrate only the red color matrices, then it is an $n-1 \times n-1$ system.
• If we repeat the same operations to get $n-2 \times n-2$ system, we require $(n-2) \times 2 \times n-1 + (n-2) \times 2 + n$ operations.
• Hence, if we would like to reduce from $k \times k$ system to $k-1 \times k-1$ system, we require $(k-1) \times 2 \times k + (k-1) \times 2 + k+1$ operations.
• To reach from $n \times n$ system to $1 \times 1$ system, we require operations.

#### Gauss Elimination

• For a $4 \times 4$ matrix, we have operations.

#### Backward/Forward Substitution

• Now let us see, how many operations required for forward/backward substitution.
• Operation Count is 1 for $x_n=\frac{y_n}{u_{nn}}$
• $\text{for } i=1,2,...,n-1$
• Number of Operation Count for $i^{th}$ step is $n-i$ multiplications and $n-i$ additions, then 1 subtraction and 1 division.
• Therefore, we require $2(n-i)+2$ operations/
• Total number of operations is
• For a unit upper/lower triangular system, we require only

#### Gaussian Elimination to solve a system

• Therefore to solve a system using Gauss Elimination method, we require $\frac{2n^3}{3}+O(n^2)$ operations.
• When the system is too large, we require more computations. For example for $n=10^6,$ we require $10^{18}$operations.

#### Doolittle/Crout/LU/Cholesky Decomposition Operation Count

• For Doolittle, Crout, Cholesky and LU Decomposition also we require $\frac{n^3}{3}+O(n)$ operations. (Exercise!)
﻿

## Theorems

#### Sufficient Condition for LU Decomposition

• If all $n$ leading principla minors of the $n \times n$ matrix $A$ are non-singular then $A$ has an LU-Decomposition.

#### Condition for Cholesky Decomposition

• If $A$ is a real, symmetric and positive definite matrix, then it has a unique ffactorization $A=LL^T$ in which $L$ is lower triangular with a positive diagonal
﻿

## Tridiagonal System

#### Tridiagonal System

• A square matrix $A=(a_{ij})$ is said to be tridiagonal if $a_{ij}=0 ~~~~ \forall~~ |i-j|>1$
$A=\begin{pmatrix} a_{11} & a_{12} & 0 & 0 & 0 & \cdots & 0 & 0 & 0\\ a_{21} & a_{22} & a_{23} & 0 & 0 & \cdots & 0 & 0 & 0\\ 0 & a_{32} & a_{33} & a_{34} & 0 & \cdots & 0 & 0 & 0\\ 0 & 0 & a_{43} & a_{44} & a_{45} & \cdots & 0 & 0 & 0\\ \vdots & \vdots & \vdots &\vdots &\vdots & \cdots & \vdots & \vdots & \vdots\\ 0 & 0 & 0 & 0 &0 & \cdots & a_{n-2n-2} & a_{n-1n-1} & a_{nn} \\ 0 & 0 & 0 & 0 & 0 & \cdots & 0 & a_{nn-1} & a_{nn} \\ \end{pmatrix}$

Using Gaussian elimination, you can develope a simple algorithm to solve this problem (Exercise: Develop an algorithm to solve this kind of matrices)

﻿

## Matrix Norm

#### Vector Norms

• On a vector space $V$ a norm is a function $\|.\|$ from $V$ to the set of nonnegative reals that obeys the following three postulats $\|x\|>0~~ \text{ if } x \neq 0, x \in V \\ \|\lambda x\|=|\lambda|\|x\|,~~\text{ if } \lambda \in \mathbb{R}, x\in V\\ \|x+y\|\leq\|x\|+\|y\|, ~~\text{ if } x,y\in V$
• Euclidean norm
• $\ell_\infty$ - norm
• $\ell_p$ - norm,
• $\ell_1$ - norm

#### Matrix Norms

• If a vector norm $\|.\|$ has been specified, the matrix norm subordinate to it is defined by
• Euclidean norm
• row sum norm
• Column sum norm

#### Condition Number and Ill-Conditioned System

• Matrix Condition number is defined by
• Well-conditioned system: A system is said to be well-conditioned if small changes on one or more of the coefficients results in a similar smaller change in the solution
• Ill-conditioned system: A system is said to be ill-conditioned if small changes on one or more of the coefficients results in a large changes in the solution
• A matrix with large condition number is said to be ill-conditioned.
• A matrix with moderate condition number is said to be well-conditioned.

An example for ill-conditioned system: A small change (perturbation) produces a big change to the solution

﻿

## Iterative Methods

#### Solution by Iteration

• For the given system $Ax = b$, we introduce a splitting matrix $Q$ that splits $A$then
• For the given initial guess $x^0$
• , we get
• If the sequence $x^{(k)}$converges to $x$, then
• By repeating we obtain
• Theorem: If $\|I-Q^{-1}A\| < 1$, we get a convergent solution for the system $Ax=b$

#### Iterative Methods

• Richardson Method $Q=I$
• Jacobi Method $Q=D$ where $D$ denotes the diagonal elements of the matrix $A$
• Gauss-Seidel Method $A = D - C_L - C_U$ $D, C_L \text{ and } C_U$ denote the diagonal elements of the matrix of $A$, the negative of strictly lower triangular part of $A$ and the negative of strictly upper triangular part of $A$ respectively $Q=D-C_L$

#### Richardson Iteration

• Input: $A,x^{(0)},M,\epsilon$
• Output: $x^{(k+1)}$

1. Initialization
2. $\text{for } k=1 \text{ to } M$
3. $~~~~~\text{for } i=1 \text{ to } n$
4. $~~~~~~~~~sum=0$
5. $~~~~~~~~~~\text{for } j=1 \text{ to } n$
6. $~~~~~~~~~~~~~~~~~~sum=sum+a_{ij}x_j$
7. $~~~~~~~~~~r_i=b_i-sum$
8. $~~~~~\text{for } i=1 \text{ to } n$
9. $~~~~~~~~~x_i=x_i+r_i$
10. $~~~~~\text{for } i=1 \text{ to } n$
11. $~~~~~~~~~norm=0$
12. $~~~~~~~~~sum=0$
13. $~~~~~~~~~~\text{for } j=1 \text{ to } n$
14. $~~~~~~~~~~~~~~~~~~sum=sum+a_{ij}x_j$
15. $~~~~~~~~~~norm=norm+(b_i-sum)^2$
16. $~~~~\text{ if } \sqrt{norm}< \epsilon$ stop

#### Jacobi Iteration

• Input: $A,x^{(0)},M,\epsilon$
• Output: $x^{(k+1)}$

1. Initialization
2. $\text{for } k=1 \text{ to } M$
3. $~~~~~\text{for } i=1 \text{ to } n$
4. $~~~~~~~~~sum=0$
5. $~~~~~~~~~~\text{for } j=1 \text{ to } n$
6. $~~~~~~~~~~~~~~~~~~sum=sum+a_{ij}x_j$
7. $~~~~~~~~~~r_i=(b_i-sum)/a_{ii}$
8. $~~~~~\text{for } i=1 \text{ to } n$
9. $~~~~~~~~~x_i=r_i$
10. $~~~~~\text{for } i=1 \text{ to } n$
11. $~~~~~~~~~norm=0$
12. $~~~~~~~~~sum=0$
13. $~~~~~~~~~~\text{for } j=1 \text{ to } n$
14. $~~~~~~~~~~~~~~~~~~sum=sum+a_{ij}x_j$
15. $~~~~~~~~~~norm=norm+(b_i-sum)^2$
16. $~~~~\text{ if } \sqrt{norm}< \epsilon$ stop

#### Gauss-Seidel Iteration

• Input: $A,x^{(0)},M,\epsilon$
• Output: $x^{(k+1)}$

1. Initialization
2. $\text{for } k=1 \text{ to } M$
3. $~~~~~\text{for } i=1 \text{ to } n$
4. $~~~~~~~~~sum=0$
5. $~~~~~~~~~~\text{for } j=1 \text{ to } n$
6. $~~~~~~~~~~~~~~~~~~\text{ if } i\neq j$
7. $~~~~~~~~~~~~~~~~~~~~~~sum=sum+a_{ij}x_j$
8. $~~~~~~~~~~x_i=(b_i-sum)/a_{ii}$
9. $~~~~~\text{for } i=1 \text{ to } n$
10. $~~~~~~~~~norm=0$
11. $~~~~~~~~~sum=0$
12. $~~~~~~~~~~\text{for } j=1 \text{ to } n$
13. $~~~~~~~~~~~~~~~~~~sum=sum+a_{ij}x_j$
14. $~~~~~~~~~~norm=norm+(b_i-sum)^2$
15. $~~~~\text{ if } \sqrt{norm}< \epsilon$ stop
﻿